The maximum occurrence of any event in the time range

Question

I have collection timestamps, for example 10:18:07.490,11:50:18.251 , where first is the start time and the second is the end time of the event. I need to find a range where maximum events occur in just 24 hours. These events occur exactly milliseconds.

What I am doing is to divide 24 hours on a millisecond scale and attach events to every millisecond, and then find the range in which the maximum events occur.

 LocalTime start = LocalTime.parse("00:00"); LocalTime end = LocalTime.parse("23:59"); 

 for (LocalTime x = start; x.isBefore(end); x = x.plus(Duration.ofMillis(1))) { for (int i = 0; i < startTime.size(); i++) { if (startTime.get(i).isAfter(x) && endTime.get(i).isBefore(x)) // add them to list; } } 

Of course, this is not a good approach; it takes up too much memory. How can i do it right? Any suggestion?

Answer 1

Solution defining the first period of maximum parallel events:

If you want to use a third-party library, this can be implemented "relatively easily" in SQL style using the jOOλ function. The idea is the same as described in amit answer :

 System.out.println( Seq.of(tuple(LocalTime.parse("10:18:07.490"), LocalTime.parse("11:50:18.251")), tuple(LocalTime.parse("09:37:03.100"), LocalTime.parse("16:57:13.938")), tuple(LocalTime.parse("08:15:11.201"), LocalTime.parse("10:33:17.019")), tuple(LocalTime.parse("10:37:03.100"), LocalTime.parse("11:00:15.123")), tuple(LocalTime.parse("11:20:55.037"), LocalTime.parse("14:37:25.188")), tuple(LocalTime.parse("12:15:00.000"), LocalTime.parse("14:13:11.456"))) .flatMap(t -> Seq.of(tuple(t.v1, 1), tuple(t.v2, -1))) .sorted(Comparator.comparing(t -> t.v1)) .window(Long.MIN_VALUE, 0) .map(w -> tuple( w.value().v1, w.lead().map(t -> t.v1).orElse(null), w.sum(t -> t.v2).orElse(0))) .maxBy(t -> t.v3) ); 

The above prints:

 Optional[(10:18:07.490, 10:33:17.019, 3)] 

So, between 10:18 ... and 10:33 ... there were three events that are the largest number of events that overlap at any time of the day.

Search for all periods of maximum simultaneous events:

Please note that there are several periods when there are 3 parallel events in the sample data. maxBy() returns only the first such period. To return all such periods, use maxAllBy() instead (added to jOOλ 0.9.11):

  .maxAllBy(t -> t.v3) .toList() 

Losing then:

 [(10:18:07.490, 10:33:17.019, 3), (10:37:03.100, 11:00:15.123, 3), (11:20:55.037, 11:50:18.251, 3), (12:15 , 14:13:11.456, 3)] 

Or a graphical representation

 3 /-----\ /-----\ /-----\ /-----\ 2 /-----/ \-----/ \-----/ \-----/ \-----\ 1 -----/ \-----\ 0 \-- 08:15 09:37 10:18 10:33 10:37 11:00 11:20 11:50 12:15 14:13 14:37 16:57 

Explanations:

Here's the original solution again with comments:

 // This is your input data Seq.of(tuple(LocalTime.parse("10:18:07.490"), LocalTime.parse("11:50:18.251")), tuple(LocalTime.parse("09:37:03.100"), LocalTime.parse("16:57:13.938")), tuple(LocalTime.parse("08:15:11.201"), LocalTime.parse("10:33:17.019")), tuple(LocalTime.parse("10:37:03.100"), LocalTime.parse("11:00:15.123")), tuple(LocalTime.parse("11:20:55.037"), LocalTime.parse("14:37:25.188")), tuple(LocalTime.parse("12:15:00.000"), LocalTime.parse("14:13:11.456"))) // Flatten "start" and "end" times into a single sequence, with start times being // accompanied by a "+1" event, and end times by a "-1" event, which can then be summed .flatMap(t -> Seq.of(tuple(t.v1, 1), tuple(t.v2, -1))) // Sort the "start" and "end" times according to the time .sorted(Comparator.comparing(t -> t.v1)) // Create a "window" between the first time and the current time in the sequence .window(Long.MIN_VALUE, 0) // Map each time value to a tuple containing // (1) the time value itself // (2) the subsequent time value (lead) // (3) the "running total" of the +1 / -1 values .map(w -> tuple( w.value().v1, w.lead().map(t -> t.v1).orElse(null), w.sum(t -> t.v2).orElse(0))) // Now, find the tuple that has the maximum "running total" value .maxBy(t -> t.v3) 

I wrote more about window functions and how to implement them in Java in this blog post .

(disclaimer: I work for jOOλ in the company)

Answer 2

This can be done much better in terms of memory (well, assuming that O (n) is considered good for you, and you do not consider 24 * 60 * 60 * 1000 an acceptable constant):

• Create a list of elements [time, type] (where time is time, and type is either start or end).
• Sort the list by time.
• Initialize the list, and when you see the "beginning", add a counter, and when you see the "end", reduce it.

By maintaining the “hitherto visible maximum,” you can easily identify one point where the maximum number of events occurs on it.

If you want to get an interval containing this point, you can simply find the time when the "first maximum" occurs until it ends (this is the next pair [time, type] or if you enable the run, complete together and do not only linear scanning from this point is taken into account until the counter decreases and time moves, this can be done only once and does not change the overall complexity of the algorithm).
It is very easy to change this approach to get an interval from a point