所有时间区间最大重叠次数

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。

- user2601967

---

难道不是有4个时间重叠吗？假设（12:14:30）应该是（12:00-14:30）。 - Andrew_CS

是的，有可以解决这个问题的算法 - 它可以用简单的贪心算法来解决。http://en.wikipedia.org/wiki/Activity_selection_problem - Benjamin Gruenbaum

@user2601967 如果您实际上回答评论中提出的问题，我们就能够理解您想要做什么，而且您也不会得到无关的回复。 - interjay

@user2601967 你不知道自己的问题是什么意思吗？ - interjay

你不知道吗？将进行关闭投票。 - Geobits

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)

- gbtimmon