算法挑战:合并日期范围

Question

我面临一个有趣的问题:

• 我有几个可以重叠的日期范围
• 他们每个人都有一个名字

是否有可能"重叠"这些范围？也就是说,生成:

• 一组新的范围,其中没有一个与其他范围重叠
• 这个新范围中的每一个都有一个相应名称的列表

也许我可以让它更具图形化.这就是我的第一个:

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

这是我想要获得的:

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

我找到了一种有效的解决方案,但不优雅:

1. 我将每个范围(从,到)转换为天数列表(d1,d2,d3等)
2. 我按天分组
3. 我聚合包含相同名称的组来重新创建范围

你能想到更好的解决方案吗？我正在使用C#,但任何与语言无关的想法都会非常感激.谢谢!

Answer 1

我会

1. 保持无序的"开放"范围列表
2. 从第1天开始,将第一个范围添加到开放范围列表中.
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---|