算法的挑戰：合併日期範圍

Question

我現在面臨一個有趣的問題：

• 我有幾個日期範圍，可以重疊他們的
• 有一個名字

是否有可能「des-overlap」這些範圍？也就是說，產生：

• 一組新的範圍，其中沒有重疊的其他
• 分別關於該新系列具有對應名稱的列表

也許我可以使這個多一點圖形。這是我第一次：

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 

這是我想獲得什麼：

|------|---------|-------|-----|-----| 
     a  a,c  a,b,c a,b b 

我發現了一個解決方案，這類作品，但是這是不優雅：

1. 我將每個範圍（從，到）轉換爲天數列表（d1，d2，d3等）
2. 我按天組名稱
3. 我彙總包含相同名稱的組以重新創建範圍

您能想到更好的解決方案嗎？我正在使用C＃，但任何語言獨立的想法將不勝感激。謝謝！

Answer 1

我會

1. 保持「開放式」的無序列表從第1天的範圍
2. 開始，第一個範圍添加到打開的範圍列表。
3. 移動到下一個範圍邊界（無論是開始還是關閉）。創建您的第一個「輸出」範圍：從第1天開始，到當天結束。它是你的開放範圍列表中的項目。
4. 如果遇到的範圍已經在打開範圍列表中，請將其刪除。否則，添加它。
5. 重複3和4，沿線移動。

我絕對做了一個不好的解釋。我將很快寫一些代碼。但在此之前，這裏的會發生在你的解決方案是什麼：

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 

 
1. Start at day 1, add A to open ranges list, which now contains [A] 
2. Move to the start of C. First RESULT RANGE: A range from Day 1 to C's start, 
     with a value A. (what is in your open ranges list) 
3. Add C to the open ranges list, which now contains [A,C] 
4. Move to the start of B. Second RESULT RANGE: A range from C's start to B's 
     start, with a value A,C. (what is in your open ranges list) 
5. Add B to the open ranges list, which now contains [A,C,B] 
6. Move to the end of C. Third RESULT RANGE: A range from B's start to C's end, 
     with a value of A,C,B. 
7. Remove C from the open ranges list, which now contains [A,B] 
8. Move to the end of A. Fourth RESULT RANGE: A range from C's end to A's end, 
     with a value of A,B 
9. Remove A from the open ranges list, which now contains [B] 
10. Move to the end of A. Fourth RESULT RANGE: A range from A's end to B's end, 
     with a value of B 

RESULT RANGES 
1. from Day 1 to C's start: A 
2. from C's start to B's start: A,C 
3. from B's start to C's end: A,C,B 
4. from C's end to A's end: A,B 
5. from A's end to B's end: B 

---

替代方法

你可以這樣做：

1. 保持「輸出範圍的有序列表」。這使得測試一個點是否在一個範圍內以及相互之間的範圍是很容易的。
2. 從您的輸入範圍取一個範圍。
3. 檢查是否完全在所有輸出範圍之前或之後，並進行相應處理。如果有，跳過下一步並返回步驟2。
4. 將其起始點與輸出範圍進行比較
5. 如果它在任何其他輸出範圍之前，請從其開始位置到第一個輸出範圍的開始位置添加一個新的輸出範圍。
6. 如果這在一個已經存在的輸出範圍之間，那麼在該點分割輸出範圍。第一部分擁有相同的「父母」，第二部分擁有相同的父母+新的輸入範圍。
7. 現在，將其終點與輸出範圍進行比較。
8. 如果它在任何其他輸出範圍之後，請添加從最後一個輸出範圍末尾到末尾的新輸出範圍。
9. 如果這在一個已經存在的輸出範圍之間，那麼在該點分割輸出範圍。第二部分將保持相同的「父母」，並且第一部分將具有相同的父母+新的輸入範圍
10. 將當前輸入範圍作爲一部分添加到步驟6中兩個「已處理」範圍之間的所有範圍和9，如果有的話。
11. 對於所有輸入範圍重複2-6。

這裏是前幾個步驟，使用所述樣本數據+另一個範圍d： （ 「處理過的」 範圍由**double stars**表示）

a |------------------------------| 
b     |-------------------| 
c   |-----------------| 
d  |------------------------| 

 

1. 
    Process A 
    Output ranges: |--------------A---------------| 
2. 
    Process B 
    - Start of B is in **A**; split A in two: 
        |-------A-------|------AB------| 
    - End of B is after any output range range; 
     creating new output range at end 
        |-------A-------|------AB------|---B---| 
    - Nothing was/is in between **A** and (nothing) 
3. 
    Process C 
    - Start of C is in **A**; split A in two: 
        |---A----|--AC--|------AB------|---B---| 
    - End of C is in **AB**; split AB in two: 
        |---A----|--AC--|--ABC--|--AB--|---B---| 
    - There were/are no ranges between **A** and **AB** 

4. 
    Process D 
    - Start of D is in **A**; split A in two: 
        |-A-|-AD-|--AC--|--ABC--|--AB--|---B---| 
    - End of D is in **AB**; split AB in two: 
        |-A-|-AD-|--AC--|--ABC--|ABD|AB|---B---| 
    - Ranges AC and ABC were/are in between **A** and **AB** 
        |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---| 

Final output:  |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---| 

Answer 2

您可能需要有看看Interval Trees 。

Answer 3

，你可以：

1. 排序的所有日期的列表（從和日期組合）
2. 然後沿着這個名單上運行，每一個新的範圍將是從一個日至下一個開始或結束日期與上述不同。

有關命名的新的範圍，這將是有意義的有，目前的新範圍包含原範圍名稱的列表，並在每次打的結束日期時間，從列表中刪除舊的範圍名稱，每一個你打到一個開始日期，將它的名字添加到列表中。

Answer 4

這樣做：

創建Event類。

class DateEvent : IComparable<DateEvent> 
{ 
    public Date Date; 
    public int DateRangeId; 
    public bool IsBegin; // is this the start of a range? 

    public int CompareTo(DateEvent other) 
    { 
     if (Date < other.Date) return -1; 
     if (Date > other.Date) return +1; 
     if (IsBegin && !other.IsBegin) return -1; 
     if (!IsBegin && other.IsBegin) return +1; 
     return 0; 
    } 
} 

定義List<DateEvent> events;

添加每個範圍的開始和結束日期到列表：

for (int i = 0; i < dateRanges.Length; ++i) 
{ 
    DateRange r = dateRanges[i]; 
    events.Add(new DateEvent(r.BeginDate, i, true)); 
    events.Add(new DateEvent(r.EndDate, i, false)); 
} 

排序的事件。

events.Sort(); 

現在成立了一個輸出類：

class OutputDateRange 
{ 
    public Date BeginDate; 
    public Date EndDate; 
    public List<string> Names; 
} 

最後，穿越事件，維護其範圍存在：

List<int> activeRanges; 
List<OutputDateRange> output; 
Date current = events[0].Date; 
int i = 0; 

while (i < events.Length;) 
{ 
    OutputDateRange out = new OutputDateRange(); 
    out.BeginDate = current; 

    // Find ending date for this sub-range. 
    while (i < events.Length && events[i].Date == current) 
    { 
     out.EndDate = events[i].Date; 
     if (events[i].IsBegin) 
      activeRanges.Add(events[i].DateRangeId); 
     else 
      activeRanges.Remove(events[i].DateRangeId); 
     ++i; 
    } 

    if (i < events.Length) 
     current = events[i].Date; 

    foreach (int j in activeRanges) 
     out.Names.Add(dateRanges[j].Name); 

    output.Add(out); 
} 

這應該做的伎倆。請注意，我沒有製作構造函數，代碼有點難看，但希望能夠傳達一般想法。

Answer 5

我有這樣做的代碼。它依靠from然後to（即，如果它是SQL，它將是ORDER BY from_value, to_value）訂購的輸入集，但在此之後它是非常優選的。

我的實現基本上做@Justin L.的answer描述，所以如果你只是想要一個文本描述，看看他的算法答案。

的代碼是在這裏：LVK.DataStructures，並且想看看文件是：

• Range.cs
• RangeExtensions.cs，特別是在​​3210及以後的切片方法。

要使用它：

List<Range<DateTime>> ranges = ... 
var slices = ranges.Slice(); 

這會給你爲每個切片一個新的範圍，併爲每個這樣的範圍內你將有包含引用回貢獻範圍內的。數據屬性。

即。對於你原來的例子，你將得到你想要的，個人範圍，在.Data屬性中的貢獻範圍a，b，c等。

這些類可能會使用我的類庫的其他部分，這些都在那裏。如果您決定使用它，只需複製您想要使用的部分。

如果您只對實施感興趣，可以在RangeExtensions.cs文件中找到line 447及之後的InternalSlice方法。

Answer 6

1. 我有一個列表第一，我不知道它的長度，但我得到了3個字符
2. 檢查一個插槽，如果A呢？添加'A'，如果B在那裏？加'B'，如果有c？加上「C」
3. 去到另一個插槽，喜歡＃2
4. 週期結束時，沒有添加到另一個新的插槽
5. 我得到的名單
6. 拉平列表