我目前面临一个有趣的问题:
是否可能将这些日期范围进行“去重叠”操作？也就是生成:
也许可以通过更加图形化的方式来描述。这是我最初的情况:
a |------------------------------|
b |-------------------|
c |-----------------|
这就是我想要得到的：
|------|---------|-------|-----|-----|
a a,c a,b,c a,b b
我找到了一种勉强可行但不够优雅的解决方案：
你有更好的解决方案吗？我在使用C#，但是任何与语言无关的想法都将不胜感激。谢谢！
我会：
我肯定没有好好解释清楚。我很快就会为此编写一些代码。但在此之前，请看一下在您的解决方案中会发生什么：
a |------------------------------|
b |-------------------|
c |-----------------|
1. 从第一天开始，加入A到开放范围列表中，现在列表为[A]
2. 移动到C的起始位置。第一个结果区间：从第一天到C的起始位置的范围，
值为A（即开放范围列表中的内容）
3. 将C添加到开放范围列表中，现在列表为[A,C]
4. 移动到B的起始位置。第二个结果区间：从C的起始位置到B的起始位置的范围，
值为A,C（即开放范围列表中的内容）
5. 将B添加到开放范围列表中，现在列表为[A,C,B]
6. 移动到C的结束位置。第三个结果区间：从B的起始位置到C的结束位置的范围，
值为A,C,B
7. 从开放范围列表中删除C，现在列表为[A,B]
8. 移动到A的结束位置。第四个结果区间：从C的结束位置到A的结束位置的范围，
值为A,B
9. 从开放范围列表中删除A，现在列表为[B]
10. 移动到A的结束位置。第五个结果区间：从A的结束位置到B的结束位置的范围，
值为B
结果区间：
1. 从第一天到C的起始位置：A
2. 从C的起始位置到B的起始位置：A,C
3. 从B的起始位置到C的结束位置：A,C,B
4. 从C的结束位置到A的结束位置：A,B
5. 从A的结束位置到B的结束位置：B
另一种方法
您可以按照以下步骤进行：
- 维护一个“输出范围”的有序列表。 这使得测试点是否在范围内以及哪些范围相互跟随变得容易。
- 获取输入范围。
- 检查它完全在所有输出范围之前或之后，如果是这样则进行处理并跳过下一步返回第2步。
- 将其起始点与输出范围进行比较。
- 如果它在任何其他输出范围之前，则添加一个新的输出范围从其起始点到第一个输出范围的起始点。
- 如果它在已存在的输出范围之间，则在该点拆分输出范围。 第一部分将保持相同的“父项”，而第二部分将具有相同的“父项”+新的输入范围。
- 现在，将其结束点与输出范围进行比较。
- 如果它在任何其他输出范围之后，则添加一个新的输出范围，从最后一个输出范围的结束点到其结束点。
- 如果它在已存在的输出范围之间，则在该点拆分输出范围。 第二部分将保持相同的“父项”，而第一部分将具有相同的“父项”+新的输入范围。
- 将当前输入范围作为步骤6和9中两个“处理过”的范围之间所有范围的一部分添加。
- 对所有输入范围重复步骤2-6。
以下是使用示例数据+另一个范围D的前几个步骤：
（用 **双星号** 表示“处理过”的范围）
<code>a |------------------------------|
b |-------------------|
c |-----------------|
d |------------------------|
</code>
1.
进程A
输出范围: |--------------A---------------|
2.
进程B
- B的开始在**A**中; 将A分为两部分:
|-------A-------|------AB------|
- B的结束在任何输出范围之后;
在结尾处创建新的输出范围
|-------A-------|------AB------|---B---|
- **A**和(无)之间没有任何内容。
3.
进程C
- C的开始在**A**中; 将A分为两部分:
|---A----|--AC--|------AB------|---B---|
- C的结束在**AB**中; 将AB分为两部分:
|---A----|--AC--|--ABC--|--AB--|---B---|
- **A**和**AB**之间没有范围
4.
进程D
- D的开始在**A**中; 将A分为两部分:
|-A-|-AD-|--AC--|--ABC--|--AB--|---B---|
- D的结束在**AB**中; 将AB分为两部分:
|-A-|-AD-|--AC--|--ABC--|ABD|AB|---B---|
- 范围AC和ABC在**A**和**AB**之间
|-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---|
最终输出: |-A-|-AD-|--ACD-|-ABCD--|ABD|AB|---B---|
from，然后按to排序(例如，如果是SQL，则为ORDER BY from_value, to_value)，但在此之后它是相当优化的。List<Range<DateTime>> ranges = ...
var slices = ranges.Slice();
您可以：
为了命名新的范围，最好有当前新范围所包含的原始范围名称列表，并且每次遇到截止日期时，从列表中删除旧的范围名称；每次遇到起始日期时，将其名称添加到列表中。
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);
}
应该就可以了。请注意，我没有创建构造函数，代码有点丑陋，但希望能传达出一般的想法。