如何不依赖排序高效检测History对象列表日期间隙？或优化现有方法

我们正在重写项目中的一项功能，核心环节是检测History对象列表中的日期间隙，后续所有操作都依赖该检测结果。History类定义如下：

public class History : IEntityBase, IEntityDates
{
    [Key]
    public long Id { get; set; }

    public DateTime? StartDate { get; set; }
    public DateTime? EndDate { get; set; }

    /* =================== 非映射属性 =================== */

    [NotMapped]
    public bool HasGap { get; set; }

    [NotMapped]
    public bool IsGapSixMonthsOrMore { get; set; }
}

日期间隙定义与检测规则 #

• 日期间隙：当两个日期（不含首尾）的间隔天数达到设定阈值时，对应History对象的HasGap属性设为true。
• 检测规则：
  • 若某History对象的EndDate为null（代表该记录仍在进行中），则所有StartDate晚于该记录StartDate的对象均不存在间隙。
  • 排序后的列表中允许存在记录重叠（比如一条记录结束时，另一条已提前2个月开始）。
  • 若histories[i].StartDate与histories[i-1].EndDate的间隔至少为7天（阈值），则该记录存在间隙。
  • 若上述间隔至少为6个月，则histories[i].IsGapSixMonthsOrMore设为true。
  • StartDate可能为null，但已在其他数据获取环节完成非空校验。

已实现的两种检测方法 #

两种方法均通过测试，其中导师的方法性能是我的两倍。

导师的实现 #

public static void CalculateGaps(this List<History> dateRanges, int? gapThreshold)
{
    if (dateRanges == null || dateRanges.Count < 2 || gapThreshold is null)
        return;

    // 按开始日期排序，再按结束日期排序
    var sortedRanges = dateRanges.OrderBy(r => r.StartDate)
        .ThenBy(r => r.EndDate)
        .ToList();

    // 第一条记录无前置历史，初始化间隙标记
    sortedRanges[0].HasGap = false;
    sortedRanges[0].IsGapSixMonthsOrMore = false;

    // 跟踪已处理记录中的最晚结束日期
    DateTime currentMaxEnd = sortedRanges[0].EndDate?.Date ?? DateTime.MaxValue;

    for (int i = 1; i < sortedRanges.Count; i++)
    {
        // 检查当前最晚结束日期与当前记录开始日期的间隙是否超过阈值
        if (currentMaxEnd < sortedRanges[i].StartDate?.Date.AddDays(-gapThreshold.Value))
        {
            sortedRanges[i].HasGap = true; // 检测到间隙

            // 判断间隙是否达到6个月及以上
            sortedRanges[i].IsGapSixMonthsOrMore = sortedRanges[i].StartDate?.Date.AddMonths(-6) >= currentMaxEnd;
        }
        else
        {
            sortedRanges[i].HasGap = false;
            sortedRanges[i].IsGapSixMonthsOrMore = false;
        }

        // 更新最晚结束日期为当前最大值或当前记录的结束日期
        var nextEnd = sortedRanges[i].EndDate?.Date ?? DateTime.MaxValue;
        currentMaxEnd = currentMaxEnd > nextEnd ? currentMaxEnd : nextEnd;
    }
}

我的实现（用队列处理多重叠记录） #

public static void CalculateGapsV2(this List<History> histories, int? gapThreshold)
{
    if (histories.Count == 0)
        return;

    histories = histories.OrderBy(h => h.StartDate).ToList();

    var queue = new Queue<DateTime?>();

    // 第一条记录无前置历史，初始化间隙标记
    histories[0].HasGap = false;
    histories[0].IsGapSixMonthsOrMore = false;

    queue.Enqueue(histories[0].EndDate?.Date);

    for (int i = 1; i < histories.Count; i++)
    {
        var previousEndDate = histories[i - 1].EndDate?.Date;
        var currentStartDate = histories[i].StartDate?.Date;

        while (queue.Count > 0)
        {
            if (queue.Peek() is null) // 存在正在进行的记录
            {
                histories[i].HasGap = false;
                histories[i].IsGapSixMonthsOrMore = false;
                break;
            }
            else if (queue.Peek() > currentStartDate)
            {
                histories[i].HasGap = false;
                histories[i].IsGapSixMonthsOrMore = false;
                queue.Enqueue(histories[i].EndDate?.Date);
                break;
            }
            else
            {
                queue.Dequeue();
            }
        }

        if (queue.Count == 0)
        {
            if (currentStartDate is null)
            {
                histories[i].HasGap = false;
                histories[i].IsGapSixMonthsOrMore = false;
            }
            else
            {
                var gapDays = (currentStartDate.Value - previousEndDate.Value).TotalDays;

                // 间隙定义为两段记录之间的完整天数：
                // 例：阈值为1时，EndDate=2024-10-1，StartDate=2024-10-2 → 无间隙；StartDate=2024-10-3 → 有间隙（中间有1天完整间隔）
                histories[i].HasGap = gapDays > gapThreshold;

                // 6个月间隙定义为间隔≥6个月：
                // 例：EndDate=2024-1-15，StartDate=2024-7-15 → 是；StartDate=2024-7-14 → 否
                histories[i].IsGapSixMonthsOrMore = currentStartDate.Value.AddMonths(-6) >= previousEndDate.Value;

                queue.Enqueue(histories[i].EndDate?.Date);
            }
        }
    }
}

问题 #

两种方法均通过测试，现咨询：

1. 是否存在不依赖列表排序的更高效日期间隙检测方式？
2. 若不存在无排序的方案，能否对导师的CalculateGaps方法做进一步优化？

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