假设你有一组区间(1,5), (6,10), (3,8), (7,9)。 我期望的输出是3,因为最多只有3个区间相交(3,8),(6,10)和(7,9)。 注意,(1,5)和(3,8)也相交,但这只有2个区间相交。因此,答案是3,因为它是最多的相交区间数。
有哪些有效的方法可以找到它?我猜第一步是根据起始值对区间进行排序。之后有什么建议吗?
有哪些有效的方法可以找到它?我猜第一步是根据起始值对区间进行排序。之后有什么建议吗?
(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)
不会被视为相交的区间。否则,它应该在之后,这些区间将被视为相交的区间。
好的,你可以根据起始时间对间隔进行排序,所以如果你有: (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;
}
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