C# 查找与DatetimeInterval列表重叠的时间区间的高效算法

优化方案 #

1 先修复现有代码的逻辑Bug #

你当前的重叠判断逻辑存在问题，两个判断条件完全重复：

newRegistration.From <= oldRegistration.To && oldRegistration.To >= newRegistration.From
上述两个条件等价，缺失了「旧区间开始时间小于等于新区间结束时间」的核心判断，正确的单区间重叠逻辑应为：

bool IsOverlap(DatetimeInterval a, DatetimeInterval b) 
    => a.From <= b.To && b.From <= a.To;

2 效率优化核心思路 #

原实现的时间复杂度为O(M*N)，M为新分块的总区间数量，N为旧区间数量，在旧区间量级较大时性能很差。我们可以通过预排序+二分查找把时间复杂度降到O(N log N + M log N)，优化逻辑如下：

• 预处理阶段仅执行1次：把所有旧区间按From属性升序排序，转换为支持随机访问的数组
• 对每个新区间，通过二分查找快速定位到所有可能重叠的旧区间范围，仅在小范围内做匹配，无需遍历全部旧区间

3 优化后完整实现 #

直接封装为你需要的扩展方法：

// 扩展方法静态类
public static class DatetimeIntervalExtensions
{
    public static List<(List<DatetimeInterval>, List<DatetimeInterval>)> FindOverlapping(
        this IEnumerable<List<DatetimeInterval>> newDateTimeChunks, 
        List<DatetimeInterval> oldDateTimes)
    {
        // 旧区间预排序：仅执行1次
        var sortedOld = oldDateTimes.OrderBy(x => x.From).ToArray();
        var result = new List<(List<DatetimeInterval>, List<DatetimeInterval>)>();

        foreach (var chunk in newDateTimeChunks)
        {
            var overlappedOld = new List<DatetimeInterval>();
            foreach (var newInterval in chunk)
            {
                // 二分查找最后一个From <= 新区间To的旧区间索引，缩小比对范围
                int left = 0, right = sortedOld.Length - 1;
                int lastPossibleIndex = -1;
                while (left <= right)
                {
                    int mid = (left + right) / 2;
                    if (sortedOld[mid].From <= newInterval.To)
                    {
                        lastPossibleIndex = mid;
                        left = mid + 1;
                    }
                    else
                    {
                        right = mid - 1;
                    }
                }

                // 从定位到的索引往前遍历，遇到旧区间结束时间早于新区间开始时间就直接停止
                for (int i = lastPossibleIndex; i >= 0; i--)
                {
                    var oldInterval = sortedOld[i];
                    if (oldInterval.To < newInterval.From)
                        break;
                    if (IsOverlap(newInterval, oldInterval))
                        overlappedOld.Add(oldInterval);
                }
            }
            // 可选去重：同一个旧区间可能和当前分块多个新区间重叠，不需要重复可保留该行
            overlappedOld = overlappedOld.Distinct().ToList();
            result.Add((overlappedOld, chunk));
        }
        return result;
    }

    // 通用重叠判断逻辑
    private static bool IsOverlap(DatetimeInterval a, DatetimeInterval b)
        => a.From <= b.To && b.From <= a.To;
}

4 调用方式 #

完全符合你要求的调用格式：

List<(List<DatetimeInterval>, List<DatetimeInterval>)> OverlappingTimeStamps = newDateTimeChunks.FindOverlapping(oldDateTimes);

额外优化建议 #

• 如果旧区间存在大量不重叠的连续区间，可以提前做区间合并，进一步减少比对次数
• 如果新分块的区间也可以提前排序，可以用双指针法把时间复杂度进一步降到O(N log N + M log M + N + M)，适合新旧区间量级都很大的场景

内容的提问来源于stack exchange，提问作者I am not Fat