如何获得两个范围的重叠范围
我在区间[1-15]中有以下范围
我想找到人1和2之间的重叠范围。
Person1 [1,3] [5,10] Person2 [2,4] [8,15]
在这里，我应该得到一个范围列表，[2,3]，[8,10]。
到目前为止我发现的是按person1的范围循环，然后按person2的范围循环，然后是每个范围的每个元素，然后使用条件测试。 这个解决方案不满足我，因为它是O（n）。 更多元素的范围，我的算法将更多地围绕每个范围的每个元素循环，如果我想看到这些范围之间的切除，则需要时间
Person1：[100000; 150000]和[90000; 140000]。 人2：[105000; 110000]和[130000; 140050]
请注意，范围在我的代码中表示为：
public class Range{ public int Start {get;set;} public int End {get;set;} } 那么找到重叠范围的最有效方法是什么？
任何帮助，将不胜感激。
PS：这里有类似的问题如何在python中找到范围重叠？ 但我不懂python代码。
看看mergesort算法的合并步骤。 如果对每个人的范围进行排序，则可以调整该方法以非常容易地计算重叠。
Loop Get the range that starts next (R1) if the next range of the other person (R2) starts before R1 ends Add the range from begin of R2 and min( end of R1 end of R2 ) to results Increase the counter for the person which gave you R1
如果已知您的范围是非相邻的（即，如果连续范围之间始终至少有一个数字）。 解决方案也将是。 否则，您可能需要额外的压缩步骤以确保将相邻范围放入一个范围。
好处是它适用于任何有序类型而不仅仅是整数，并且您可以非常快地交叉任意数量的范围（O（n + m））。
对范围的开始和结束进行排序..保持信息以及是否为范围开始或结束……对于您的示例，您将得到：
1 start 2 start 3 end 4 end 5 start 8 start 10 end 15 end
现在循环遍历这些点并保持一个计数器.. + 1表示结束的开始-1。 此计数器是任何时候重叠段的数量。 如果您想要每次增加或减少计数器时需要测试的边界。 如果你将它从1增加到2，这是一个重叠范围的开始..重叠范围的结束将是你将计数器从2减少到1
马丁
谢谢你的澄清。 这样的事情……
public static IList GetListIntersections(IList rangeList1, IList rangeList2) { var intersection = new List (); //add intersection of each range foreach (var x in rangeList1) { foreach (var y in rangeList2) { var intersect = GetIntersection(x, y); if (intersect != null) { intersection.Add(intersect); } } } //remove ranges that are subsets of other ranges intersection.RemoveAll(x => intersection.Any(y => y != x && y.Start >= x.Start && y.End <= x.End)); return intersection; } public static Range GetIntersection(Range range1, Range range2) { int greatestStart = range1.Start > range2.Start ? range1.Start : range2.Start; int smallestEnd = range1.End < range2.End ? range1.End : range2.End; //no intersection if (greatestStart > smallestEnd) { return null; } return new Range { Start = greatestStart, End = smallestEnd }; }
我不明白你是怎么循环’person1的范围，然后是person2的范围’ – 我不知道这意味着什么意思没有看到代码。
我看不出你会如何比O（n）更好，但是你只能在范围内迭代一次。 更好的数据结构可能是bool[]或BitArray 。
var person1 = new bool[15] { /* set values */ }; var person2 = new bool[15] { /* set values */ }; var overlap = new bool[15]; for (int i = 0; i < 15; i++) { overlap[i] = person1[i] && person2[i]; }