algorithm - 如何找到具有公共(public)点的这些间隔的最大数量？

Question

我一直在复习算法，这是 Anany Levitin 的算法书中的问题..

You have a list of n open intervals (a1, b1), ... , (an, bn) on the real line. (An open interval (a, b) comprises all the points strictly between its endpoints a and b, i.e., (a, b)= (xi a< x < b}.) Find the maximal number of these intervals that have a common point. For example, for the intervals (1, 4), (0, 3), ( -1.5, 2), (3.6, 5), this maximal number is 3. Design an algorithm for this problem with a better than quadratic time efficiency.

任何人都可以帮我形成一个算法或建议互联网上的任何资源..

谢谢，哈伦德拉

Answer 1

解决此问题的一种方法如下:假设您要在实数线上排列所有间隔。从最左边开始，扫描间隔。每次输入间隔时，都会增加事件间隔数的计数器，每次离开时，都会减少计数器。在此过程中计数器的最大值就是您要查找的数字。

要实现这一点，请将区间的所有起点和终点(一起)排序到一个长度为 2n 的巨大列表中，该列表包含所有线段出现时的起点和终点。然后，从左到右扫描列表，根据您找到的点更新计数器(+1 表示起点，-1 表示终点)。排序需要 O(n log n) 时间，扫描需要 O(n) 时间，总共需要 O(n log n) 时间。

希望这对您有所帮助!