算法的挑战：合并日期范围

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. 拉平列表