1

问题描述如下：

特定日期 d 有 n 个事件，具有开始时间和持续时间。例子：

e1 10:15:06 11ms (ms = milli seconds)
e2 10:16:07 12ms
......

我需要找出时间x和n。其中 x 是执行最大事件的时间。

我在想的解决方案是： 在第 d 天扫描所有毫秒。但是该请求总共计算了 86400000*n。例子

Check at 00::00::00::001 How many events are running
Check at 00::00::00::002 How many events are running
Take max of Range(00::00::00::01,00::00::00::00)

我想的第二个解决方案是：

For eventi in all events
   Set running_event=1
   eventj in all events Where eventj!=eventi
        if eventj.start_time in Range (eventi.start_time,eventi.execution_time)
           running_event++

然后取最大的 running_event

有没有更好的解决方案？

4

2 回答 2

2

这个可以及时解决O(n log n)：

  • 制作所有事件的数组。该数组已经部分排序：O(n)
  • 对数组进行排序：O(n log n); 您的图书馆应该能够利用部分排序（timSort做得很好）；研究基于分布的排序算法以获得更好的预期运行时间。
    • 按边界时间升序对事件边界进行排序
    • 如果触摸间隔被认为不重叠，排序事件在排序开始之前结束（如果触摸间隔被认为重叠，排序事件在排序开始后结束）
  • 初始化running= 0, running_best= 0, best_at= 0
  • 对于每个事件边界：
    • 如果是事件的开始，则递增running
    • 如果running > running_best, 设置best_at= 当前事件时间
    • 如果是事件的结束，则递减running
  • 输出best_at
于 2012-12-23T07:59:00.870 回答
0

您可以通过仅检查所有间隔的结束来减少检查的点数，对于从到I持续的每个间隔（任务） ，您只需要检查有多少任务正在运行（假设任务从到包含，如果是独占的，请检查.t1t2t1t2t1t2t1-EPSILON, t1+EPSILON, t2-EPSILON, T2+EPSILON

很容易看出（说服自己为什么），如果这些案例没有涵盖，您将无法得到更好的结果。

例子：

tasks run in `[0.5,1.5],[0,1.2],[1,3]`
candidates: 0,0.5,1,1.2,1.5,3
0 -> 1 tasks
0.5 -> 2 tasks
1 -> 3 tasks
1.2 -> 3 tasks (assuming inclusive, end of interval)
1.5 -> 2 tasks (assuming inclusive, end of interval)
3 -> 1 task (assuming inclusive, end of interval)
于 2012-12-23T07:58:34.863 回答