LeetCode 1229. 安排会议日程

2026-05-10 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1229. 安排会议日程

题意分析

题目目标：给两个人各自的空闲时间段列表 slots1、slots2，以及会议时长 duration。要在两人都空闲的时间里挑出一个长度恰为 duration 的区间，返回最早的那个 [start, start + duration]；不存在就返回空数组。

核心约束：时间段列表没有说是有序的，但题目保证同一个人的空闲段互不重叠。「互不重叠」这条比「有序」更值钱——它意味着只要排一次序，两个列表就都变成了单调递增且互不相交的区间序列，扫描时可以放心地「用完就丢」。另一个信号是数据规模到 $10^4$，$O(mn)$ 的两两求交（$10^8$）在最坏情况下会超时，必须做到线性或接近线性。

边界处理：交集可能为空（end - start 是负数），要用 >= duration 而不是先判空再比较；duration 可能大于任何一段的长度，此时全程无解；两个列表中任一为空则直接无解；返回的是恰好 duration 长度的区间，不是整个交集。

实现取舍：暴力两两求交是 $O(mn)$，排序后双指针是 $O(m\log m + n\log n)$。后者的额外收益是天然按时间从早到晚扫描，第一个满足条件的交集自动就是最早答案，不用再比较。

解法：排序 + 双指针

核心思路

暴力做法很直白：枚举 slots1 的每一段、slots2 的每一段，求交集 [max(起点), min(终点)]，长度够就记录，最后取起点最小的那个。正确但要跑 $m \times n$ 次，$10^4 \times 10^4$ 直接爆掉。

瓶颈在哪？暴力枚举把大量根本不可能相交的组合也算了一遍。比如 slots1 的第一段在 [10, 50]，而 slots2 里有段在 [1000, 2000]，这种组合算了也是白算。

关键观察：把两个列表都按开始时间升序排好之后，考察当前的一对段 A = slots1[i]、B = slots2[j]。假设它们的交集不够长，那么谁先结束，谁就注定出局。为什么？设 A.end < B.end，那么 slots1 中排在 A 后面的段起点都 $\ge$ A.end（同一人的段互不重叠且已排序），所以 A 和 slots2 中排在 B 之后的任何段都不可能相交——那些段的起点都 $\ge$ B.start，而 A 已经在 B.end 之前就结束了，A 能贡献的最好交集就是刚才算的那个，既然不够长，A 就可以永久丢弃。

于是不变量是：任何时刻，最优解（若存在）一定落在 slots1[i..] 与 slots2[j..] 这两个后缀之间。每次丢弃的段都已经被证明「和所有还没考察的对手都无法产生更长的交集」，所以丢弃是安全的。指针 i、j 各自单调右移，总移动次数不超过 $m + n$。

再补一条：因为两侧都按开始时间递增扫描，第一次找到的合法交集，其起点就是全局最小的可行起点，直接返回即可，不需要继续找更早的。

解题步骤

第一步：把 slots1 和 slots2 分别按开始时间升序排序。 为什么：上面那条「先结束者出局」的推理，前提是「后面的段起点更晚」。输入未保证有序，不排序这条推理就不成立，指针右移就会丢掉真正的答案。

第二步：i = 0、j = 0，进入 i < m && j < n 的循环。 为什么用 &&：任一列表扫完，剩下的段就没有配对对象了，继续扫描没有意义。

第三步：算当前交集 start = max(slots1[i][0], slots2[j][0])、end = min(slots1[i][1], slots2[j][1])。 为什么是「起点取大、终点取小」：交集是两个区间共同覆盖的部分，必须晚于两者中较晚的开始，早于两者中较早的结束。两段不相交时会算出 end < start，这是合法的中间状态，不需要特判。

第四步：若 end - start >= duration，立刻返回 [start, start + duration]。 为什么返回 start + duration 而不是 end：题目要的是恰好 duration 长的会议，不是整个空闲交集。为什么可以立刻返回：见上文，扫描顺序保证了它就是最早解。

第五步：否则比较 slots1[i][1] 和 slots2[j][1]，结束更早的一侧指针右移。 为什么只移一侧：结束更晚的那段仍然可能和对方后续的段相交，丢掉它会漏解。为什么相等时移哪边都行：两段同时结束，两者都无法再和对方的后续段相交，代码里走 else 分支移 j，下一轮 slots1[i] 会立刻和新的 slots2[j] 比较并同样被淘汰，结果不受影响。

第六步：循环自然结束说明无解，返回空数组。

以 slots1 = [[10,50],[60,120],[140,210]]、slots2 = [[0,15],[60,70]]、duration = 8 走一遍：两个列表已经有序。i=0, j=0，当前段 [10,50] 与 [0,15]，start = max(10,0) = 10，end = min(50,15) = 15，长度 5 < 8。比较结束时间：50 > 15，slots2[0] 先结束，它被淘汰——因为 slots1 后面的段起点都 $\ge 60 > 15$，不可能再和 [0,15] 相交。j 变成 1。

i=0, j=1，当前段 [10,50] 与 [60,70]，start = max(10,60) = 60，end = min(50,70) = 50，end - start = -10，两段压根不相交，负值自然小于 8。比较结束时间：50 < 70，slots1[0] 先结束被淘汰，i 变成 1。

i=1, j=1，当前段 [60,120] 与 [60,70]，start = max(60,60) = 60，end = min(120,70) = 70，长度 10 $\ge$ 8，命中。返回 [60, 60+8] = [60, 68]，与期望一致。

再把 duration 改成 12 走一遍尾巴：前三步同上，到 i=1, j=1 时长度 10 < 12，比较结束时间 120 > 70，j 变成 2 越界，循环退出，返回 []。注意这里 slots1[2] = [140,210] 根本没被访问过——它没有任何对手了，跳过是正确的。

代码实现

class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
        Arrays.sort(slots2, (a, b) -> a[0] - b[0]);

        int i = 0;
        int j = 0;
        while (i < slots1.length && j < slots2.length) {
            int start = Math.max(slots1[i][0], slots2[j][0]);
            int end = Math.min(slots1[i][1], slots2[j][1]);
            if (end - start >= duration) {
                return Arrays.asList(start, start + duration);
            }
            if (slots1[i][1] < slots2[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        return new ArrayList<>();
    }
}

func minAvailableDuration(slots1 [][]int, slots2 [][]int, duration int) []int {
    sort.Slice(slots1, func(i, j int) bool { return slots1[i][0] < slots1[j][0] })
    sort.Slice(slots2, func(i, j int) bool { return slots2[i][0] < slots2[j][0] })

    i, j := 0, 0
    for i < len(slots1) && j < len(slots2) {
        start := max(slots1[i][0], slots2[j][0])
        end := min(slots1[i][1], slots2[j][1])
        if end-start >= duration {
            return []int{start, start + duration}
        }
        if slots1[i][1] < slots2[j][1] {
            i++
        } else {
            j++
        }
    }
    return []int{}
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(m \log m + n \log n)$。凭什么：两次排序是主导项；随后的双指针扫描中 i 和 j 都只增不减，每轮至少有一个前进，循环体是 $O(1)$，因此扫描只需 $O(m + n)$，被排序的开销吸收。

空间复杂度：$O(\log m + \log n)$。凭什么：算法本身只用了 i、j、start、end 四个标量，额外空间全部来自排序的递归栈——Java 的 Arrays.sort 对对象数组用 TimSort（最坏 $O(m)$ 的临时数组）、Go 的 sort.Slice 用内省排序（$O(\log m)$ 栈）。若不计排序，则是严格的 $O(1)$。

关键点总结

「区间互不重叠 + 已排序」是双指针的通行证。 有了这两条，才能断言「被淘汰的段和所有未访问的对手都无法产生更好的结果」，指针单向移动才安全。

淘汰规则永远盯住「谁先结束」，而不是「谁先开始」。 结束早的那段失去了所有未来机会，结束晚的还留在场上——这是所有区间双指针题（求交、求并、求覆盖）共用的直觉。

交集用「起点取 max、终点取 min」统一表达，不相交自然表现为负长度。 不需要写 if (a.end < b.start) continue 这类特判，少一个分支就少一个出错点。

有序扫描下的第一个可行解就是最优解。 认出这一点才敢 return 而不是继续维护全局最小值，代码短一半。

返回值语义要抠字眼。 题目要 [start, start + duration] 而不是完整交集，这类「答案是可行解的一个截取」在区间题里很常见。

面试视角：这题的标准答法是先给 $O(mn)$ 暴力并说明它为什么不行，再引出排序 + 双指针，重点讲清楚「为什么丢掉先结束的那段不会漏解」——面试官考的就是这条交换论证。如果时间充裕，可以补一句变体：若两人变成 $k$ 个人，双指针不再适用，应改为把所有段拆成 (时间点, +1/-1) 事件后扫描线求「同时空闲人数 = k」的区间。

易错点总结

错误写法：不排序直接双指针 → 用例 slots1 = [[60,120],[10,50]]、slots2 = [[0,15],[60,70]]、duration = 8，首轮比较 [60,120] 与 [0,15]，交集为负，120 > 15 于是 j++，接着 [60,120] 与 [60,70] 交集 10 命中，看似侥幸对了；但换成 slots1 = [[60,120],[10,50]]、slots2 = [[60,70],[0,15]] 时首轮就淘汰了 slots2[1]，随后 [10,50] 无对手，返回 []，漏掉正确答案。

错误写法：end - start > duration 用了严格大于 → 用例 slots1 = [[10,18]]、slots2 = [[10,18]]、duration = 8，交集恰好 8，被判不合格返回 []，正确答案是 [10,18]。

错误写法：返回 [start, end] 而不是 [start, start + duration] → 用例 slots1 = [[60,120]]、slots2 = [[60,70]]、duration = 8，返回 [60,70] 而非 [60,68]，长度不等于 duration 被判错。

错误写法：淘汰时比较开始时间 slots1[i][0] < slots2[j][0] → 用例 slots1 = [[0,100]]、slots2 = [[1,2],[10,30]]、duration = 10，首轮交集 [1,2] 不够，因 0 < 1 而 i++，slots1 立刻扫完返回 []，但正确答案是 [10,20]。

错误写法：无论如何都同时 i++ 且 j++ → 用例 slots1 = [[0,100]]、slots2 = [[1,2],[10,30]]、duration = 10，一轮之后两个指针一起越界，返回 []，同样漏解。

错误写法：while (i < m || j < n) 用了或 → 用例 slots1 = [[10,50]]、slots2 = [[0,15],[60,70]]，i 越界后仍进入循环体访问 slots1[1]，抛出 ArrayIndexOutOfBoundsException / Go 的 index out of range。

错误写法：Arrays.sort(slots1, (a, b) -> a[0] - b[0]) 在时间戳可能为负或极大时用减法比较 → 本题时间为 $[0, 10^9]$ 尚不溢出，但同样写法迁移到含负数或 Integer.MIN_VALUE 的题上会因减法溢出得到错误顺序，应写 Integer.compare(a[0], b[0])。

错误写法：找到合法交集后不返回而是继续扫描，最后取 start 最小者 → 逻辑上不错，但用例 slots1 = [[10,50]]、slots2 = [[10,50]]、duration = 5 里若忘了初始化全局答案或比较条件写反，会返回后来的、更晚的区间而不是最早的。

错误写法：Java 里返回 Arrays.asList(start, start + duration) 之后又对它调用 add/remove → Arrays.asList 返回的是定长视图，会抛 UnsupportedOperationException；无解分支必须另建 new ArrayList<>()。

相似题目

题目	难度	考察点
56. 合并区间	中等	排序后处理的是同一列表内部的相邻重叠，不涉及两列表配对
252. 会议室	简单	只需判断是否存在重叠，不需要求交集长度
253. 会议室 II	中等	用最小堆或差分统计同时重叠的最大层数，双指针不适用
435. 无重叠区间	中等	按结束时间排序做贪心删除，淘汰依据是「保留结束早的」而非「丢弃结束早的」
759. 员工空闲时间	困难	推广到 $k$ 个人，需要扫描线或多路归并，两指针退化
986. 区间列表的交集	中等	同样是两列表双指针求交，但要求输出全部交集而非最早的一个