我在区间 [1-15] 中有以下范围
我想找到人 1 和人 2 之间的重叠范围。
人物 1 [1, 3] [5, 10]
人物 2 [2, 4] [8, 15]
这里我应该得到一个范围列表，其中 [2,3], [8, 10]。
到目前为止我发现的是先按 person1 的范围循环，然后按 person2 的范围循环，然后针对每个范围的每个元素循环，然后使用条件测试。
这个解决方案并不令我满意，因为它的复杂度为 O(n)。元素范围越多，我的算法就会对每个范围的每个元素进行循环，如果我想查看这些范围之间的切面，这将需要时间
人1：[100000； 150000]和[90000； 140000]。
人2：[105000； 110000]和[130000； 140050]
请注意，我的代码中的范围表示为：
public class Range{
public int Start {get;set;}
public int End {get;set;}
}
那么找到重叠范围的最有效方法是什么？
任何帮助，将不胜感激。
PS：这里有类似的问题如何在Python中找到范围重叠？ https://stackoverflow.com/questions/6821156/how-to-find-range-overlap-in-python但我不明白 python 代码。
对范围的开始和结束进行排序...保留有关其是否是范围开始或结束的信息...对于您的示例，您将得到以下信息：
1 start
2 start
3 end
4 end
5 start
8 start
10 end
15 end
现在循环这些点并保留一个计数器.. +1 表示开始 -1 表示结束。该计数器是任意时间重叠段的数量。如果您想要边界，则需要在每次增加或减少计数器时进行测试。如果将其从 1 增加到 2，则这是重叠范围的开始。重叠范围的结束将是当您将计数器从 2 减少到 1 时
Martin
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
