给定一组区间,如何找到它们之间的最大交点数, [英] Given a set of intervals, how to find the maximum number of intersections among them,
问题描述
假设您有一组区间 (1,5)、(6,10)、(3,8)、(7,9).我期望的输出是 3,因为最多有 3 个间隔 (3,8)、(6,10) 和 (7,9) 彼此相交.请注意,(1,5) 和 (3,8) 也彼此相交,但这只是其中的 2 个.所以这里的答案将是 3,因为 3 是彼此相交的最大间隔数.
Let's say you are given a set of intervals (1,5), (6,10), (3,8), (7,9). The output I expect is 3 since there are maximum 3 intervals (3,8), (6,10) and (7,9) that intersect with each other. Note that, (1,5) and (3,8) also intersect with each other but that's only 2 of them. So the answer here is going to be 3, since 3 is the maximum number of intervals that intersect with each other.
有哪些有效的方法可以找到它?我想第一步是根据起始值对间隔进行排序.之后有什么建议吗?
What are some efficient ways of finding it? I guess the first step would be to sort the intervals according to the starting value. Any suggestions after that?
推荐答案
标准的解决方案是将区间处理成一组(开始,结束)点.例如 (1,3)
生成 {1, begin}
, {3, end}
.然后对点进行排序并从左到右扫描,将 begin
计为 +1,将 end
计为 -1.计数器达到的最大值为最大重叠间隔数.
The standard solution is to process the intervals into a set of (begin,end) points. For example (1,3)
generates {1, begin}
, {3, end}
. Then sort the points and scan left to right, counting begin
as +1, end
as -1. The max value reached by the counter is the maximum number of overlapping intervals.
这是从问题中的示例生成的中间数组:
This is the intermediate array generated from the example in the question:
[(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)
不会算作相交.否则它应该在后面,这些间隔将被视为相交间隔.
There is a minor tricky point here. Does (1,end)
go before or after (1,begin)
? If you treat intervals as open, then it should go before - this way (0,1)
& (1,2)
won't be counted as intersecting. Otherwise it should go after and these intervals will count as intersecting ones.
这篇关于给定一组区间,如何找到它们之间的最大交点数,的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!