I'm trying to efficiently compute events in a time series by grouping them into buckets. My goal is to have as few buckets as possible. The constraint is that events within one bucket are all within a 30 minute time window.
To get more concrete, let's assume I've got these events:
time | event |
---|---|
15:15 | 1 |
16:58 | 2 |
17:13 | 3 |
17:21 | 4 |
A naive approach to group those events into 30 minute intervals would result in these 3 buckets
bucket 1: 15:00-15:30 – event 1
bucket 2: 16:30-17:00 – event 2
bucket 3: 17:00-17:30 – event 3,4
A better solution with fewer buckets is possible though:
bucket 1: 15:00-15:30 – event 1
bucket 2: 16:58-17:28 – event 2,3,4
What kind of algorithm do I need to look for to efficiently find the fewest amount of buckets for this kind of data?
I'd prefer a fast solution (i.e less than $O(n^2)$) over an optimal one.