最近在一次采访中有人问我这个问题。虽然我是上不来的 Ø （ ñ ²）的解决方案，面试官与一个痴迷 Ø （ ñ ）解决方案。我还检查了我了解的
O （ n log n ）的其他解决方案，但是 O （ n ）解决方案仍然不是我的杯茶，它假定约会按开始时间排序。

有人可以解释吗？

问题陈述： 给您 n个 约会。每个约会都包含开始时间和结束时间。您必须有效地重新安排所有有冲突的约会。

人：1、2、3、4、5
应用开始：
2、4、29、10、22应用结束：5、7、34、11、36

答案：2x1 5x3

O （ n log n ）算法：像这样分开起点和终点：

2s，4s，29s，10s，22s，5e，7e，34e，11e，36e

然后对所有这些点进行排序（为简单起见，我们假设每个点都是唯一的）：

2s，4s，5e，7e，10s，11e，22s，29s，34e，36e

如果我们有连续的起点而没有终点，那么它是重叠的：2s，4s相邻，所以有重叠

我们将保留一个“ s”的计数，每次遇到它都会+1，当遇到e时，我们将计数减少1。