给定一组区间，如何找到它们之间最大的相交数量？

Question

假设你有一组区间(1,5), (6,10), (3,8), (7,9)。 我期望的输出是3，因为最多只有3个区间相交(3,8)，(6,10)和(7,9)。 注意，(1,5)和(3,8)也相交，但这只有2个区间相交。因此，答案是3，因为它是最多的相交区间数。

有哪些有效的方法可以找到它？我猜第一步是根据起始值对区间进行排序。之后有什么建议吗？

- Asif Iqbal

---

这是一个标准的面试问题，已经被问过和回答过数百次了。在发帖之前，请尝试搜索一下。 - Salvador Dali

Answer 1

标准解决方案是将时间段处理为一组（开始，结束）点。例如，（1,3） 生成 {1, 开始}，{3, 结束}。然后对这些点进行排序并从左到右扫描，将 开始 计为 +1，将 结束 计为 -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)不会被视为相交的区间。否则，它应该在之后，这些区间将被视为相交的区间。

- Rafał Dowgird

Answer 2

好的，你可以根据起始时间对间隔进行排序，所以如果你有： (1,5) , (4,8) , (2,3)

它们会被排序为： (1,5) , (2,3) , (4,8)

然后，你将检查每个间隔的开始时间是否与你找到的最高结束时间相交。 如果开始时间小于结束时间，则存在交集。

int highestEnd = intervals[0].end; // The highest end would be the end of the first interval
int numOfIntersections = 0;
for(int i = 1; i < intervalsSize; i++){
    if(intervals[i].start < highestEnd)
         numOfIntersections++;
    if(intervals[i].end > highestEnd)
         highestEnd = intervals[i].end;
}

- Khaled Hamdy

---

谢谢你的回答。然而，我认为这里有一个缺陷。在你的解决方案中，你从未重置变量“numberOfIntersections”。假设排序后它看起来像这样：(1,5)，(3,8)，(7,10)，(15,20)，(17,25)，(23,28)，(25,30)。在这种情况下，你的算法将输出7，而期望的答案是4。前3个元组处于交集中，后4个元组也处于交集中，但这两个组是不相交的。我认为在你的算法中，每当条件“intervals[i].start < highestEnd”失败时，我们应该将“numberOfIntersections”重置为0。 - Asif Iqbal

Answer 3

希望这对你有用：（Python代码）- 经过测试可以正常工作 概述：我根据开始时间进行排序，并找到间隔结束时间的最小值。

def max_intersections(intervals):
max_simultaneous = 0
intersections = 0
smallest_end = intervals[0].end
intervals.sort(key=lambda x: x.start)
for i in range(len(intervals)):
    if intervals[i].start < smallest_end:
        smallest_end = min(smallest_end, intervals[i].end)
        intersections += 1
    else:
        max_simultaneous = max(max_simultaneous, intersections)
return max_simultaneous

- sree