给定一组间隔，如何找到它们之间的最大交点数， [英] 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屋！