时间范围内任何事件的最大发生次数

Question

我有收集时间戳,例如10:18:07.490,11:50:18.251,第一个是开始时间,第二个是事件的结束时间.我需要找到一个范围,其中最大事件发生在24小时之内.这些事件以毫秒的精度发生.

我所做的是以毫秒级划分24小时,并在每毫秒附加事件,然后找到发生最大事件的范围.

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;
        }

    }

当然这不是一个好方法,它需要太多的记忆.我怎么能以适当的方式做到这一点？有什么建议吗？

Answer 1

找到最大并发事件的第一个周期的解决方案:

如果您愿意使用第三方库,可以使用jOOλ的窗口函数以SQL风格"相对简单"实现.这个想法与amit的答案中解释的相同:

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)
);

以上打印:

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

因此,在10:18 ...和10:33之间的时间段内,有3个事件,这是在白天任何时间重叠的事件数量最多的事件.

查找最大并发事件的所有时段:

请注意,样本数据中有3个并发事件有几个时间段.maxBy()只返回第一个这样的时期.为了返回所有这些时期,请使用maxAllBy()(添加到jOOλ0.9.11):

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

然后屈服:

[(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)]

或者,图形表示

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

说明:

这是原始解决方案的评论:

// 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)

我已经在这篇博客文章中写了更多关于窗口函数以及如何用Java实现它们的内容.

(免责声明:我为jOOλ背后的公司工作)