c# - 算法挑战 : merging date range

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,B9.  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 BRESULT RANGES1. from Day 1 to C's start: A2. from C's start to B's start: A,C3. from B's start to C's end: A,C,B4. from C's end to A's end: A,B5. from A's end to B's end: B

---

Alternative Method

You could do this:

1. Keep a ordered list of "output ranges". This makes it easy to test if a point is within a range, and also what ranges follow eachother.
2. Take a range from your input ranges.
3. Check to see if it is completely before or completely after all output ranges, and handle accordingly. Skip the next steps and go back to step 2, if so.
4. Compare its start point to the output ranges
5. If it is before any other output range, add a new output range from its start to the start of the first output range.
6. If this is in between an already-existing output range, split that output range at that point. The first part would hold the same "parents", and the second part would have the same parents + the new input range.
7. Now, compare its end point to the output ranges.
8. If it is after any other output range, add a new output range from the end of the last output range to its end.
9. If this is in between an already-existing output range, split that output range at that point. The second part would hold the same "parents", and the first part would have the same parents + the new input range
10. Add the current input range as a part to all ranges in between the two "processed" ranges in steps 6 and 9, if any.
11. Repeat 2-6 for all input ranges.

Here are the first few steps, using the sample data + another range D:("processed" ranges indicated by **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---|