自上而下範圍合併？

Question

我要合併一些間隔是這樣的：

>>> ranges = [(30, 45), (40, 50), (10, 50), (60, 90), (90, 100)] 
>>> merge(ranges) 
[(10, 50), (60, 100)] 

我不是在CS野戰。我知道如何通過迭代來實現，但是想知道是否有更高效的「自上而下」方法來更有效地合併它們，也許使用某種特殊的數據結構？

謝謝。

Answer 1

是的，有效的方法是使用interval tree。

Answer 2

區間樹確實有效，但它比您需要的更復雜。間隔樹是「在線」的解決方案，所以它可以讓你添加一些間隔，看工會，加入更多的時間間隔，再看看，等

如果你把所有的時間間隔前期，你可以做一些簡單的：

1. 開始與輸入

   範圍= [（30，45），（40，50），（10，50）]

2. 轉換範圍列表轉換的列表端點。如果你有範圍（A，B），你可以將它轉換爲兩個端點：（A，0）將是左端點，（B，1）將是正確的端點。

   端點= [（30，0），（45，1），（40，0），（50，1），（10,0），（50，1）]

3. 排序端點

   端點= [（10，0），（30，0），（40，0），（45，1），（50，1），（50，1）]

4. 掃描轉發到端點列表。當您看到左端點時遞增計數器，當您看到正確的端點時遞減計數器。每當計數器達到0時，就關閉當前的合併時間間隔。

該解決方案可以在幾行中實現。

Answer 3

以下算法在C＃做你想做的。它使用DateTime間隔範圍，但您可以根據自己的喜好進行調整。按照升序開始順序對收集進行排序後，如果下一個時間間隔的開始時間是前一個時間間隔的開始時間或之前的時間，它們會重疊，並且如果需要，可以延長結束時間。否則它們不會重疊，並且將前一個保存到結果中。

public static List<DateTimeRange> MergeTimeRanges(List<DateTimeRange> inputRanges) 
{ 
    List<DateTimeRange> mergedRanges = new List<DateTimeRange>(); 

    // Sort in ascending start order. 
    inputRanges.Sort(); 

    DateTime currentStart = inputRanges[0].Start; 
    DateTime currentEnd = inputRanges[0].End; 

    for (int i = 1; i < inputRanges.Count; i++) 
    { 
    if (inputRanges[i].Start <= currentEnd) 
    { 
     if (inputRanges[i].End > currentEnd) 
     { 
     currentEnd = inputRanges[i].End; // Extend range. 
     } 
    } 
    else 
    { 
     // Save current range to output. 
     mergedRanges.Add(new DateTimeRange(currentStart, currentEnd)); 

     currentStart = inputRanges[i].Start; 
     currentEnd = inputRanges[i].End; 
    } 
    } 

    mergedRanges.Add(new DateTimeRange(currentStart, currentEnd)); 

    return mergedRanges; 
}