给定一组间隔，如何找到它们之间的最大交点数，

Question

假设您获得了一组间隔（1,5），（6,10），（3,8），（7,9）。我期望的输出是3，因为最多有3个彼此相交的区间（3,8），（6,10）和（7,9）。请注意，（1,5）和（3,8）也相交，但这只是其中的2个。因此，这里的答案将是3，因为3是彼此相交的最大间隔数。

有哪些有效的查找方法？我想第一步将是根据起始值对时间间隔进行排序。之后有什么建议吗？

Answer 1

标准解决方案是将间隔处理为一组（起点，终点）点。例如(1,3)生成{1, begin}，{3, end}。然后对这些点进行排序，并从左到右扫描，计数begin为+1，计数end为-1。计数器达到的最大值是重叠间隔的最大数量。

这是从问题示例生成的中间数组：

[(1, 'begin'),
 (3, 'begin'),
 (5, 'end'),
 (6, 'begin'),
 (7, 'begin'),  # <--- counter reaches 3, its maximum value here.
 (8, 'end'),
 (9, 'end'), (10, 'end')]

这里有一个小技巧。是(1,end)去之前还是之后(1,begin)？如果您将间隔视为开放的，那么它应该在此之前-这样(0,1)，(1,2)并且不会被视为相交。否则，它应该继续下去，并且这些间隔将被视为相交的间隔。