如何獲得兩個範圍重合範圍

下列範圍內，我想找到的人之間的重疊範圍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]。 Person2：[105000; 110000]和[130000; 140050]

注意一個範圍在我的代碼表示爲：

public class Range{ 
    public int Start {get;set;} 
    public int End {get;set;} 
}

那麼什麼是最有效的方式找到重複區域？

任何幫助，將不勝感激。

PS：這裏有類似的問題How to find range overlap in python?但我不明白python代碼。

來源

2011-09-15 Gui

你怎麼知道是否存在更多的重疊或沒有檢查每個n個範圍？ – dlev

我認爲他的意思是n是元素的範圍，而不是範圍的數量。例如，沒有迭代2000次並測試每個元素，[1,1000]與[100,2000]的重疊是什麼。他想計算僅迭代範圍（在本例中爲兩個）的相交範圍，而不是元素（其中的2000個）。 – hatchet

短斧是正確的，我要編輯我的帖子，使其更清晰 – Gui

看看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））。

來源

2011-09-16 13:14:21 LiKao

我不明白你是如何循環'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]; 
}

來源

2011-09-15 23:48:34

如果範圍排序，他可以走兩個人的範圍，比較他目前正在看person1人範圍，留在範圍與移動到具有較低值的人的下一個範圍。這將計算交叉口，而不是15個步驟。 – hatchet

@hatchet這是真的，但大哦是一個上限 - 或'最壞的情況'。如果'範圍'像[1] [3] [5]等，那麼會有比這個方法更多的步驟。兩者都是O（n）。注意我只是建議我認爲是一種更清晰的描述他的數據的方法 - 循環BitArray的速度非常快。 –

我同意最糟糕的情況會有類似的成本，最壞的情況是[1,1] [2,2] [3,3] ...，但最好的和平均的情況將會是最差的情況。在典型情況下，走距離可能會更有效率。 – hatchet

排序的啓動和範圍的兩端..一起保持信息是否它的範圍，開始或完成...您的例子中，你會得到這樣的：

1 start 
2 start 
3 end 
4 end 
5 start 
8 start 
10 end 
15 end

現在循環這些點並保持一個計數器。+1爲一個結束開始-1。此計數器是任何時候重疊片段的數量。如果您希望每次增加或減少計數器時都需要測試邊界。如果從1到2增加它這是一個重疊範圍的開始..當你降低計數器從2到1

馬丁

來源

2011-09-16 00:26:05

感謝澄清重疊範圍的結束會。那麼像這樣的事情......

public static IList<Range> GetListIntersections(IList<Range> rangeList1, IList<Range> rangeList2) 
{ 
    var intersection = new List<Range>(); 

    //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 }; 
}

來源

2011-09-16 01:43:53 codeConcussion

我有一個範圍的IList。我需要檢索 – Gui

如何獲得兩個範圍重合範圍

回答

相關問題