2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks a lot! Yes this solution seems fairly trivial in hindsight 😅. Maybe due to having a background in machine learning, I wasn't really able to frame it properly. (My mind was stuck on on k-means-clustering like approaches, but that's not really what this issue was about!) $\endgroup$
    – Daniel
    Jan 20 at 10:20
  • 2
    $\begingroup$ You're welcome! I think most people occasionally gets stuck on an easy problem by looking for a complicated solution :) $\endgroup$
    – Tassle
    Jan 20 at 10:26
  • $\begingroup$ @Daniel You can even use the counting sort for sorting in $O(n)$ time since there are only 1440 different time entries $\endgroup$ Jan 20 at 10:30
  • $\begingroup$ thanks for the hint @Inuyashayagami, but my use case also includes the date of the event, so the provided answer is pretty much exactly what I'm looking for :) $\endgroup$
    – Daniel
    Jan 20 at 10:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.