如何获取LargeInterval与多个SmallInterval的非相交区间？

类型定义 #

LargeInterval 类

public class LargeInterval 
{
    public DateTime StartPeriod { get; set; }
    public DateTime EndPeriod { get; set; }
}

SmallInterval 类

public class SmallInterval
{
    public DateTime From { get; set; }
    public DateTime To { get; set; }
}

示例数据 #

大区间实例

LargeInterval interval = new LargeInterval
{
    StartPeriod = DateTime.Today,
    EndPeriod = DateTime.Today.AddYears(1),
};

小区间实例

SmallInterval s1 = new SmallInterval
{
    From = DateTime.Parse("2024-05-01"),
    To = DateTime.Parse("2024-07-03")
};

SmallInterval s2 = new SmallInterval
{
    From = DateTime.Parse("2024-08-01"),
    To = DateTime.Parse("2024-10-03")
};

需求说明 #

获取LargeInterval与所有SmallInterval的非相交区间，预期结果示例：

• DateTime.Today 至 2024-04-30
• 2024-07-04 至 2024-07-31
• 2024-10-04 至 DateTime.Today.AddYears(1).AddDays(-1)

现有未完成代码 #

DateTime startPeriod = interval.StartPeriod;
DateTime endPeriod = interval.EndPeriod;

IEnumerable<SmallInterval> existingPeriodsIntersectingTheNewPeriod = smallIntervals
    .Where(x => x.From <= endPeriod && x.To >= startPeriod)
    .OrderBy(x => x.From);

foreach (var stsp in existingPeriodsIntersectingTheNewPeriod)
{
    // 待完善的场景处理逻辑
}

完善后的完整实现 #

通过跟踪当前区间起始点，逐个处理排序后的小区间，可完整提取所有非相交区间：

// 存储非相交区间的结果集合
var nonOverlappingIntervals = new List<(DateTime Start, DateTime End)>();

DateTime currentStart = interval.StartPeriod;
DateTime largeIntervalEnd = interval.EndPeriod;

// 筛选并排序与大区间相交的小区间（按起始时间升序）
var sortedIntersectingSmallIntervals = smallIntervals
    .Where(x => x.From < largeIntervalEnd && x.To > currentStart)
    .OrderBy(x => x.From)
    .ToList();

foreach (var smallInterval in sortedIntersectingSmallIntervals)
{
    // 当前起始点早于小区间起始，存在非相交间隙
    if (currentStart < smallInterval.From)
    {
        nonOverlappingIntervals.Add((currentStart, smallInterval.From.AddDays(-1)));
    }

    // 更新当前起始点为小区间结束的后一天
    currentStart = smallInterval.To.AddDays(1);

    // 当前起始点已超出大区间范围，提前终止循环
    if (currentStart >= largeIntervalEnd)
    {
        break;
    }
}

// 处理大区间末尾的剩余非相交部分
if (currentStart < largeIntervalEnd)
{
    nonOverlappingIntervals.Add((currentStart, largeIntervalEnd.AddDays(-1)));
}

// 输出结果示例
foreach (var gap in nonOverlappingIntervals)
{
    Console.WriteLine($"{gap.Start:yyyy-MM-dd} until {gap.End:yyyy-MM-dd}");
}

核心逻辑说明 #

1. 排序预处理：将与大区间相交的小区间按起始时间升序排列，保证按顺序处理间隙。
2. 间隙检测：对比当前起始点与小区间起始点，若存在时间差，该差值即为非相交区间。
3. 起始点更新：每次处理完一个小区间后，将当前起始点移至小区间结束的后一天，避免重复计算。
4. 末尾收尾：循环结束后，若当前起始点仍在大区间范围内，将该段剩余时间加入结果集合。
5. 边界修正：通过AddDays(-1)和AddDays(1)调整区间边界，确保非相交区间与原小区间无重叠。

内容的提问来源于stack exchange，提问作者Akhtubir