algorithm - 所有时间间隔的最大重叠数

Question

给定一组时间间隔，如何找到最大重叠数。是否有任何算法可以解决时间复杂度 O(n log n) 或 O(n) 的给定问题？

示例：(6:00-9:30)、(9:00-12:30)、(10:00-10:30)、(12:00-14:30)、(11:00-13:30) ). 答案是 3

Answer 1

使用快速排序 --O(nlogn)时间对值进行排序。

 6:00(+)
 9:30(-)
 9:00(+)
12:30(-)
10:00(+)
10:30(-)
12:14:30(Dude wut?) --> Im going to assume you meant 12:00(+) ,14:30(-)
11:00(+)
13:30(-)

变成

 6:00(+)
 9:00(+)
 9:30(-)
10:00(+)
10:30(-)
11:00(+)
12:00(+)
12:30(-)
13:30(-)
14:30(-)

遍历列表，每加一次递增，每减一次递减，记录找到的最大值。这需要O(n)时间

总时间O(nlogn + n) = O(nlogn)