Group time series events into minimal amount of buckets

Question

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.

Answer 1

The first event at time $t_0$ needs to be in a bucket. We can safely choose the bucket $[t_0, t_0+30]$, as there is nothing to gain by making it start earlier. We then move on to the next event starting at $t>t_0+30$ (earlier events fall into the bucket we chose). We once again choose the latest bucket containing that event. It is not hard to prove that repeating this strategy until all events are covered is optimal (you can do it by induction).

This procedure runs in $O(n)$ time if your events are sorted, $O(n\log(n))$ if you need to sort them first.