用差分数组解决会议室预订冲突：TypeScript 实现区间加法与扫描线检测重叠

问题场景

会议室预订系统中，用户提交多个时间段。需要判断同一时刻的会议数量是否超过会议室容量（比如只有 2 间可用）。如果超过，要找出冲突的时间段。例如：

• A: 09:00-10:00
• B: 09:30-10:30
• C: 10:00-11:00
• D: 09:45-09:50

容量为 2 时，09:45-09:50 同时有 A、B、D 三个会议，冲突。

直接两两比较区间是 O(n^2)，当预订量较大时不够高效。差分数组配合扫描线可以在 O(n log n) 时间内完成检测（排序端点）。核心思想：把每个预订看作在时间轴上对区间 [start, end) 加 1，然后求每个时间点的并发数；超过容量即为冲突。

为什么用差分数组与扫描线

差分数组擅长处理「区间加法，最后求每个位置的值」。对于离散的时间点，如果我们在 diff[start] 加 1，在 diff[end] 减 1，那么前缀和就能还原每个时间点的覆盖次数。

但会议时间是连续的，并发数只在端点之间变化。因此，先收集所有 start 和 end，排序去重，得到一组离散的坐标点。任意两个相邻坐标点之间，并发数不变。这样就把连续区间压缩成离散区间，再用差分数组求每个离散区间的并发数。这也是一种扫描线思路。

TypeScript 实现

下面代码可直接在 Node.js 环境运行。时间使用「分钟数」作为整数占位值，实际项目可替换为时间戳。

type Booking = {
  id: string;
  start: number; // 左闭，单位：分钟
  end: number;   // 右开，单位：分钟
};

type Conflict = {
  start: number;
  end: number;
  count: number;
};

function addRange(diff: number[], start: number, end: number, value: number): void {
  if (start >= end) return;
  diff[start] += value;
  if (end < diff.length) {
    diff[end] -= value;
  }
}

function detectConflicts(bookings: Booking[], capacity: number): Conflict[] {
  const points = new Set<number>();
  for (const b of bookings) {
    if (b.start < b.end) {
      points.add(b.start);
      points.add(b.end);
    }
  }

  const sorted = Array.from(points).sort((a, b) => a - b);
  const index = new Map<number, number>();
  sorted.forEach((t, i) => index.set(t, i));

  const diff = new Array(sorted.length).fill(0);
  for (const b of bookings) {
    if (b.start >= b.end) continue;
    const l = index.get(b.start)!;
    const r = index.get(b.end)!;
    addRange(diff, l, r, 1);
  }

  const conflicts: Conflict[] = [];
  let current = 0;

  for (let i = 0; i < sorted.length - 1; i++) {
    current += diff[i];
    if (current > capacity) {
      const start = sorted[i];
      const end = sorted[i + 1];
      const last = conflicts[conflicts.length - 1];

      if (last && last.end === start && last.count === current) {
        last.end = end;
      } else {
        conflicts.push({ start, end, count: current });
      }
    }
  }

  return conflicts;
}

// 测试
const bookings: Booking[] = [
  { id: 'A', start: 9 * 60, end: 10 * 60 },
  { id: 'B', start: 9 * 60 + 30, end: 10 * 60 + 30 },
  { id: 'C', start: 10 * 60, end: 11 * 60 },
  { id: 'D', start: 9 * 60 + 45, end: 9 * 60 + 50 },
];

const conflicts = detectConflicts(bookings, 2);
console.log(conflicts);

运行方法：

1. 安装 Node.js 和 TypeScript 环境。
2. 将代码保存为 meeting-conflict.ts。
3. 使用 npx ts-node meeting-conflict.ts 直接运行；或者 npx tsc meeting-conflict.ts --target ES2020 && node meeting-conflict.js。
4. 预期输出类似：

[
  { start: 585, end: 590, count: 3 }
]

这里 585 分钟是 09:45，590 是 09:50。容量为 2，该区间有 3 个重叠，因此冲突。

代码要点解析

• 左闭右开：预订 [start, end) 表示从 start 开始，到 end 结束但不包含 end。这样 A 的 10:00 结束和 C 的 10:00 开始不会算作重叠，符合大多数会议室场景。
• 离散化：只取所有 start 和 end 作为关键点。两个关键点之间的并发数恒定，不需要逐分钟遍历。
• 差分数组：addRange 在 start 索引加 1，在 end 索引减 1。前缀和扫描时，current 就是当前离散区间的并发数。
• 冲突合并：如果相邻离散区间都超过容量且并发数相同，就合并成一个更大的冲突区间，减少输出碎片。
• 容量判断：current > capacity 表示超出容量。如果容量为 2，当前并发为 3 就是冲突。

边界与限制

1. 时间单位：示例使用整数分钟。如果实际时间包含秒或毫秒，建议统一转换为最小整数单位（如毫秒时间戳），避免浮点数精度问题。
2. 无效区间：start >= end 的预订应提前过滤或视为无效。
3. 静态批量：差分数组适合一次性检测一批预订。如果预订会频繁动态插入和删除，每次重建差分数组可能不划算，可考虑平衡树、线段树或时间轮等结构。
4. 容量为 0：如果容量为 0，任何有效预订都会冲突，代码仍能返回所有区间，但业务上通常不会这样设置。
5. 跨天预订：示例假设所有时间在同一天且时间戳连续。跨天需要先按天切分或使用完整时间戳。
6. 输出含义：冲突区间只表示并发数超过容量，不区分具体是哪些预订冲突。如果需要列出冲突的预订 ID，可以在扫描时维护活动集合，但会增加复杂度。
7. 内存：离散化后的数组长度最多为 2n，内存占用与预订数量线性相关。

小结

差分数组把区间加法转化为端点增减，扫描线把连续时间压缩为离散区间。两者结合，可以清晰地检测会议室预订冲突，并输出冲突时间段。示例代码保持最小可运行，便于替换时间类型和冲突处理策略。在实际系统中，还需要结合业务规则，例如是否允许排队、是否自动拒绝、是否支持跨天等，但核心的区间重叠检测逻辑可以复用本文的实现。