C#实现阈值触发式预约时间线项生成的问题求助

问题描述 #

给定存在时间重叠的预约列表，需按以下规则生成对应状态的时间线项：

• 每日统计时段固定为08:00-18:00
• 状态阈值规则：
  • OK：同时段预约数 ≤1
  • Warning：同时段预约数 =2
  • Error：同时段预约数 ≥3
• 要求每次占用率阈值变化时生成新的时间线项，当前实现存在生成错误、占用率计算异常问题，且逐分钟遍历的方式效率极低，需替换为高效方案。

核心方案：事件点扫描法 #

放弃逐分钟遍历的低效方式，改用事件点扫描法：提取所有预约的开始/结束时间点（加上每日时段边界），排序后扫描相邻时间点的区间，计算区间内的预约重叠数，再生成对应状态的时间线项。该方案时间复杂度为O(n log n)（主要来自事件点排序），远优于逐分钟遍历的O(1440n)，且能精准捕捉所有状态变化节点。

实现步骤 #

1. 收集关键事件点

   • 提取每个预约的StartTime和EndTime，并将其截断到当日08:00-18:00范围内（比如预约早于08:00则取08:00，晚于18:00则取18:00）
   • 为每个有效预约添加两个事件：开始事件（重叠数+1）、结束事件（重叠数-1）
   • 添加当日时段的起始（08:00）和结束（18:00）作为边界事件

2. 排序事件点

   • 将所有事件点按时间先后排序，确保扫描顺序正确

3. 扫描区间生成时间线项

   • 初始化当前重叠数currentOverlap = 0，记录上一个时间点prevTime
   • 遍历每个事件点：
     • 若prevTime与当前事件点时间存在有效区间（在08:00-18:00内且时长>0），根据当前重叠数确定区间状态，生成对应的TimeLineItem
     • 更新currentOverlap（加上事件的Delta值），并将prevTime更新为当前事件点时间

代码示例 #

假设使用以下类定义：

public enum Color { Green, Yellow, Red }
public class Reservation { public DateTime StartTime; public DateTime EndTime; }
public class TimeLineItem { 
    public DateTime Start { get; set; }
    public DateTime End { get; set; }
    public Color StatusColor { get; set; }
}

实现函数：

public List<TimeLineItem> GenerateTimeLineItems(List<Reservation> reservations, DateTime targetDate)
{
    var timeLineItems = new List<TimeLineItem>();
    var dayStart = new DateTime(targetDate.Year, targetDate.Month, targetDate.Day, 8, 0, 0);
    var dayEnd = new DateTime(targetDate.Year, targetDate.Month, targetDate.Day, 18, 0, 0);

    // 收集所有事件点：(时间, 重叠数变化量)
    var events = new List<(DateTime Time, int Delta)>();
    foreach (var res in reservations)
    {
        // 修正预约时间到当日统计范围内
        var actualStart = res.StartTime < dayStart ? dayStart : res.StartTime;
        var actualEnd = res.EndTime > dayEnd ? dayEnd : res.EndTime;
        if (actualStart >= actualEnd) continue; // 跳过完全在时段外的无效预约

        events.Add((actualStart, 1));
        events.Add((actualEnd, -1));
    }
    // 添加时段边界事件，确保覆盖整个统计区间
    events.Add((dayStart, 0));
    events.Add((dayEnd, 0));

    // 按时间排序事件点
    events.Sort((a, b) => a.Time.CompareTo(b.Time));

    int currentOverlap = 0;
    DateTime prevTime = dayStart;

    foreach (var evt in events)
    {
        var currTime = evt.Time;
        // 处理两个时间点之间的有效区间
        if (prevTime < currTime && prevTime < dayEnd && currTime > dayStart)
        {
            // 确保区间完全在统计时段内
            var intervalStart = prevTime < dayStart ? dayStart : prevTime;
            var intervalEnd = currTime > dayEnd ? dayEnd : currTime;
            if (intervalStart >= intervalEnd)
            {
                prevTime = currTime;
                continue;
            }

            // 根据重叠数映射状态
            Color statusColor = currentOverlap switch
            {
                <=1 => Color.Green,
                2 => Color.Yellow,
                _ => Color.Red
            };

            timeLineItems.Add(new TimeLineItem
            {
                Start = intervalStart,
                End = intervalEnd,
                StatusColor = statusColor
            });
        }

        // 更新当前重叠数
        currentOverlap += evt.Delta;
        prevTime = currTime;
    }

    return timeLineItems;
}

关键注意事项 #

• 边界截断：必须将预约时间限制在08:00-18:00内，避免生成超出统计范围的时间线项
• 无效预约过滤：直接跳过完全在统计时段外的预约，减少不必要的计算
• 事件顺序：同一时间点的事件顺序不影响结果，因为区间是左闭右开的[prevTime, currTime)，事件的变化只会影响下一个区间的重叠数
• 状态准确性：每个区间的状态由进入该区间时的重叠数决定，确保状态与实际占用率完全匹配

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