LeetCode 757. 设置交集大小至少为2

2022-08-31 HGNULB 约 14 分钟

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

分类

题目描述

✅ 757. 设置交集大小至少为2

题意分析

给定若干个闭区间 intervals[i] = [l, r]，要构造一个整数集合 $S$，使得每一个区间与 $S$ 的交集至少含有两个元素，求 $S$ 的最小可能大小。

先把「集合」这个词的含义钉死：$S$ 里的元素互不相同，所以同一个整数不能被计两次。这一点在实现时特别容易被踩——某个区间只差一个点时，如果错误地把已经在 $S$ 里的点又「加」了一次，计数就虚增了，而且更严重的是 $S$ 的实际状态与你以为的状态脱节了。

「至少两个」是这道题相对于经典打点问题的唯一升级，但它把状态从「记住最后放的那一个点」变成了「记住最后放的那两个点」。这个 2 不是可有可无的数字，它决定了贪心状态的维数。如果题目改成至少 $k$ 个，状态就要记最后 $k$ 个点。

约束是 $1 \le n \le 3000$，$0 \le l < r \le 10^8$。区间数只有三千，$O(n \log n)$ 或 $O(n^2)$ 都能过；但值域到 $10^8$ 意味着绝不能按坐标建数组或做区间 DP，答案里的点必须直接从区间端点上取，不能靠枚举坐标。同时 $l < r$ 保证了每个区间至少含两个整数，问题永远有解——最坏情况是每个区间各贡献两个点。

边界方面：单个区间的答案恒为 2；两个完全相同的区间答案仍是 2；两个不相交区间答案是 4。这些都应该由统一的贪心流程得出，不需要特判。

解法：排序 + 贪心维护最后两个点

核心思路

暴力思路是把所有可能的点集枚举一遍取最小，这显然不可行；退一步，用区间 DP 或最小覆盖模型也会被 $10^8$ 的值域卡死。真正的瓶颈在于：我们并不需要「知道 $S$ 的全貌」，只需要在处理每个区间时判断「当前已选的点里，落在这个区间内的有几个」。

顺着这个瓶颈找突破口。如果把区间按右端点升序处理，就会出现一个极强的性质：当处理到区间 $[l, r]$ 时，之前所有已放置的点，都是为右端点不超过 $r$ 的区间服务的，而为了让点尽量被后面的区间复用，每次放点都应该放在尽可能靠右的位置。于是已放置的点中，只有最大的那两个可能落在当前区间内——比它们更小的点，如果连它们都没进当前区间，就更不可能进了。

这就给出了状态定义：用两个变量 $s$ 与 $e$ 分别记录已选集合 $S$ 中第二大和最大的元素（初始都取 $-1$，表示尚未选点）。整个算法的不变量是：处理完前 $i$ 个区间后，$S$ 已经满足这 $i$ 个区间的要求，且 $s < e$ 是 $S$ 中最大的两个元素，$e$ 不超过已处理区间中最大的右端点。

有了这个状态，每个新区间 $[l, r]$ 只需三种情形：

$l \le s$：说明 $s$ 和 $e$ 都不小于 $l$；又因为排序保证 $s < e \le r$，两者都落在 $[l, r]$ 内，交集已经够 2 个，什么都不用做。

$s < l \le e$：只有 $e$ 落在区间内，还差一个点。新点取 $r$——取最右端是为了让它对后续（右端点更大的）区间的可复用性最强。放完后最大的两个点变成 $e$ 和 $r$，所以 $s \leftarrow e$、$e \leftarrow r$，答案加一。

$l > e$：$s$ 和 $e$ 都在区间左侧，一个都用不上，必须新放两个点。取 $r-1$ 和 $r$——这是区间内最靠右的两个整数，理由同上。放完后 $s \leftarrow r-1$、$e \leftarrow r$，答案加二。这里用到了 $l < r$ 的约束保证 $r - 1 \ge l$，两个点都在区间内。

为什么「取最右」是对的？考虑任意一个最优解，把它在当前区间内选的点向右平移到区间右端，得到的仍是一个合法解且规模不变——因为向右移动只可能让这些点被更多的、右端点更大的后续区间包含，绝不会让已处理的区间失去覆盖（已处理区间的右端点都不超过 $r$，但这些区间在处理时已被满足，它们的点没有被动过）。这就是经典的交换论证。

还剩一个不显然但致命的细节：右端点相同的区间之间，必须按左端点降序处理。原因是，右端点相同的一组区间中，左端点越大的区间越「窄」、约束越紧；先处理窄的，放下的点会自动落进宽的区间里；反过来先处理宽的，放下的点可能落在窄区间的左边，等轮到窄区间时又得重新放点，而且更糟的是可能触发「把 $r$ 重复放入」的退化状态，让 $s$ 和 $e$ 变成同一个值，破坏「$s < e$」这条不变量，此后的判断全部失真。所以排序键是右端点升序、左端点降序。

解题步骤

第一步，按右端点升序、左端点降序排序。 为什么右端点升序：这是贪心「取最右」成立的前提，它保证当前区间的右端点不小于此前所有放过的点，从而 $s < e \le r$ 恒成立，三种情形的判断才只需比较左端点。为什么左端点降序：右端点相同时先处理更窄的区间，否则会出现同一个点被重复放置、状态退化的错误。

第二步，初始化 $s = -1$、$e = -1$、$answer = 0$。 为什么用 $-1$：题目保证 $l \ge 0$，所以 $-1$ 比任何左端点都小，第一个区间必然落入「$l > e$」分支，自然地放下两个点，无需特判空集。

第三步，遍历排序后的每个区间，取出 $l$ 与 $r$。

第四步，若 $l \le s$，跳过。 为什么只比 $s$ 就够：$s$ 是两个点中较小的那个，$s \ge l$ 就意味着 $e$ 也 $\ge l$；而两者都 $\le e \le r$，所以两个点都在区间内。

第五步，否则若 $l \le e$，答案加一，令 $s \leftarrow e$、$e \leftarrow r$。 为什么新点取 $r$ 而不取区间内其它位置：取最右端使它被后续区间复用的概率最大，由交换论证保证不劣。为什么更新顺序是先 $s \leftarrow e$ 再 $e \leftarrow r$：新的最大值是 $r$，次大值是原来的 $e$；顺序写反会丢掉旧的 $e$。

第六步，否则答案加二，令 $s \leftarrow r-1$、$e \leftarrow r$。 为什么是 $r-1$ 和 $r$：区间内最靠右的两个整数，且由 $l < r$ 保证 $r-1 \ge l$ 一定落在区间内。

第七步，遍历结束返回 $answer$。 为什么不需要真的把点存进集合：贪心过程中每个点只在放下的那一刻被计数一次，且「取最右」保证了新放的点严格大于当前的 $e$，永不重复，所以计数与集合大小一致。

以 intervals = [[1,3],[1,4],[2,5],[3,5]] 走一遍。

排序：右端点依次是 3、4、5、5。右端点为 5 的两个区间 [2,5] 与 [3,5] 按左端点降序，[3,5] 排在前。最终顺序为 [1,3]、[1,4]、[3,5]、[2,5]。

处理 [1,3]：$s = e = -1$，$l = 1 > e = -1$，落入第三种情形。答案加二变成 2，$s = 3 - 1 = 2$，$e = 3$。此时 $S = {2, 3}$，区间 [1,3] 的交集是 ${2,3}$，恰好两个。

处理 [1,4]：$l = 1 \le s = 2$，跳过。验证一下：$S \cap [1,4] = {2,3}$，确实已有两个，无需加点。这一步展示了「取最右」的收益——如果第一步把点放在 1 和 2，这里同样够用，但下一步会更吃亏。

处理 [3,5]：$l = 3 > s = 2$，不能跳过；$l = 3 \le e = 3$，落入第二种情形，说明只有 $e = 3$ 这一个点在区间内。答案加一变成 3，$s \leftarrow 3$，$e \leftarrow 5$。此时 $S = {2, 3, 5}$，$S \cap [3,5] = {3,5}$，两个，达标。

处理 [2,5]：$l = 2 \le s = 3$，跳过。验证：$S \cap [2,5] = {2,3,5}$，三个，达标。这一步正是左端点降序排序的收益——如果先处理了更宽的 [2,5]，它会因为 $l = 2 \le s = 2$ 而被直接跳过，随后处理 [3,5] 时又得单独补点，虽然本例结果相同，但在别的输入上会直接算错。

最终返回 3，对应集合 ${2, 3, 5}$，可以逐一验证四个区间的交集大小分别是 2、2、3、2，全部达标，且 3 是最小值（[1,3] 与 [3,5] 只共享点 3，两者合起来至少需要 $2 + 2 - 1 = 3$ 个点）。

代码实现

class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] != b[1] ? a[1] - b[1] : b[0] - a[0]);

        int answer = 0;
        int s = -1;
        int e = -1;

        for (int[] it : intervals) {
            int l = it[0];
            int r = it[1];

            if (l <= s) {
                continue;
            }
            if (l <= e) {
                answer += 1;
                s = e;
                e = r;
            } else {
                answer += 2;
                s = r - 1;
                e = r;
            }
        }

        return answer;
    }
}

func intersectionSizeTwo(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][1] != intervals[j][1] {
            return intervals[i][1] < intervals[j][1]
        }
        return intervals[i][0] > intervals[j][0]
    })

    answer := 0
    s, e := -1, -1

    for _, interval := range intervals {
        l, r := interval[0], interval[1]

        if l <= s {
            continue
        }
        if l <= e {
            answer++
            s = e
            e = r
        } else {
            answer += 2
            s = r - 1
            e = r
        }
    }

    return answer
}

复杂度分析

时间复杂度：$O(n \log n)$。开销全在排序上；随后的单遍扫描每个区间只做常数次比较与赋值，是 $O(n)$。$n \le 3000$ 时排序不到 $4 \times 10^4$ 次比较，扫描三千次，压力极小。

空间复杂度：$O(\log n)$。算法本身只用了 $s$、$e$、$answer$ 三个整型变量，是 $O(1)$；额外的对数项来自排序实现的递归栈（Java 对对象数组用的是归并类排序，会有 $O(n)$ 的临时数组，Go 的 sort.Slice 是原地快排，栈深 $O(\log n)$）。注意我们没有真正存储集合 $S$，只靠两个变量就足以做出所有决策，这是贪心相对于构造式解法的最大节省。

关键点总结

「至少 $k$ 个」把贪心状态从一个点扩展到 $k$ 个点。经典打点题（每个区间至少一个点）只需记住最后放的那一个，本题要求 2 就得记住最后两个。识别出这个维度关系，题目从「不会做」变成「模板加一维」，$k$ 更大时同理维护一个长度为 $k$ 的有序窗口。

按右端点排序 + 取最右端放点，是区间打点类问题的统一范式。这两件事互为前提：排序保证了「已放的点不会超出当前区间右界」，取最右保证了「已放的点尽可能被后续区间复用」。正确性靠交换论证——把最优解中的点右移不会变劣。

同键次序会改变贪心结果，必须显式论证。右端点相同时按左端点降序，不是可有可无的美化，而是正确性要求：先处理约束更紧的区间，才能避免为宽区间放的点白白浪费、进而引发重复放点。凡是排序驱动的贪心，都要问一句「主键相同时谁先谁后有区别吗」。

贪心状态要维持严格的不变量。这里的不变量是「$s < e$ 是 $S$ 中最大的两个元素」。一旦某次更新让 $s = e$，后续的三分支判断就全部失去意义。写完贪心后逐条检查每个分支是否维持了不变量，是最有效的自查手段。

值域大而元素少时，答案的候选一定来自输入端点。$10^8$ 的坐标范围排除了任何按值域展开的做法，反过来提示「点只会取在 $r$ 或 $r-1$ 上」。这个思路在离散化、扫描线、区间贪心里反复出现。

面试视角：这题的难点在讲清两处正确性，而不是写出十几行代码。第一处是「为什么取最右端」，要给出交换论证而不是说「感觉更划算」；第二处是「为什么同右端点要按左端点降序」，最好当场给一个反例（见易错点第一条），因为这是区分「背过题解」和「真的想明白了」的分水岭。若面试官把 2 改成 $k$，要能立刻答出：状态变为维护 $S$ 中最大的 $k$ 个点，每次按已覆盖数量补足差额，从 $r$ 往左依次放点，复杂度变成 $O(nk + n \log n)$。

易错点总结

错误写法：排序时右端点相同按左端点升序（或不指定次序）。以 intervals = [[3,4],[2,4],[6,8],[4,6],[5,6]] 为例，升序排出 [2,4],[3,4],[4,6],[5,6],[6,8]：处理 [4,6] 时补点 $r = 6$，得 $s = 4$、$e = 6$；处理 [5,6] 时 $l = 5 > s = 4$ 且 $l \le e = 6$，又补一个 $r = 6$，于是 $s$ 和 $e$ 双双变成 6——同一个点被计了两次，且不变量 $s < e$ 被破坏；接着 [6,8] 因 $l = 6 \le s = 6$ 被跳过，但实际 $S \cap [6,8]$ 只有一个点。最终返回 4，而正确答案是 5。这是本题最隐蔽也最致命的错误。

错误写法：按左端点排序而不是右端点。以 intervals = [[1,3],[3,5]] 为例，若按左端点升序处理 [1,3] 放 ${2,3}$、[3,5] 补一个 5，得 3，碰巧正确；但换成 [[1,10],[2,3]]，先处理 [1,10] 放 ${9,10}$，再处理 [2,3] 时两个点都在右侧，只能再放 ${2,3}$，返回 4，而正确答案是 2（取 ${2,3}$ 即可满足两个区间）。右端点升序是「取最右」贪心成立的前提，不能替换。

错误写法：第二种情形新点取 $l$ 或区间中点而非 $r$。以 intervals = [[1,3],[3,5],[4,6]] 为例，处理 [3,5] 时若补点取 $l = 3$（已存在，实际等于没加）或取中点 4，得 $S = {2,3,4}$；再处理 [4,6] 时只有 4 在内，还要补两个点，总数达 5，而取 $r = 5$ 的正确流程得到 $S = {2,3,5,6}$ 共 4 个。取最右才能最大化复用。

错误写法：第三种情形放 $l$ 和 $l+1$。以 intervals = [[1,5],[4,6]] 为例，第一个区间放 ${1,2}$，第二个区间一个都用不上，再放两个，共 4；正确做法放 ${4,5}$ 后第二个区间只需补 6，共 3。

错误写法：第一种情形的判断写成 $l \le e$（用最大值而非次大值）。以 intervals = [[1,3],[3,5]] 为例，处理 [3,5] 时 $s = 2$、$e = 3$，$l = 3 \le e$ 会被误判为「已经够两个」而跳过，返回 2；但 $S = {2,3}$ 与 [3,5] 的交集只有 ${3}$ 一个元素，正确答案是 3。判「够两个」必须看次大值。

错误写法：第二种情形的更新顺序写反成 $e \leftarrow r$ 后再 $s \leftarrow e$。以 intervals = [[1,3],[3,5],[5,7]] 为例，处理 [3,5] 时会得到 $s = e = 5$，旧的 $e = 3$ 丢失，不变量破坏；接着 [5,7] 因 $l = 5 \le s = 5$ 被跳过，返回 3，而 $S$ 实际只有 ${2,3,5}$，与 [5,7] 的交集仅一个元素，正确答案是 4。

错误写法：初始 $s$、$e$ 设为 0。以 intervals = [[0,2]] 为例，$l = 0 \le s = 0$ 直接跳过，返回 0，而正确答案是 2。题目允许 $l = 0$，哨兵必须严格小于任何可能的左端点。

错误写法：Java 排序比较器写成 a[1] - b[1]（直接相减）。虽然本题 $r \le 10^8$ 不会溢出，但一旦值域放大到接近 Integer.MAX_VALUE，两个异号大整数相减会溢出成相反符号，排序结果彻底错乱且不报错。养成用 Integer.compare 的习惯，或至少确认值域安全。

错误写法：第三种情形用 $r-1$ 时不检查 $r-1 \ge l$。本题由 $l < r$ 的约束保证安全，但若把解法迁移到允许 $l = r$ 的变体，$r - 1$ 会落到区间外，得到一个不满足约束的解。迁移时必须重新确认这个前提。

错误写法：真的用一个集合存 $S$ 并每次遍历统计交集大小。以 $n = 3000$ 的输入为例，每个区间都要扫一遍集合，退化成 $O(n^2)$ 甚至更差；更麻烦的是引入了「点可能重复插入」的正确性风险。贪心的价值恰恰在于只用两个变量就概括了全部有效信息。

错误写法：跳过分支里顺手更新 $e \leftarrow r$。以 intervals = [[2,3],[1,10]] 为例，处理 [1,10] 时本应跳过且不动状态，若把 $e$ 更新成 10，$S$ 实际并没有 10 这个点，状态与现实脱节；后续区间 [9,11] 会因 $l = 9 \le e = 10$ 而只补一个点，返回 3，而正确答案是 4。跳过就是什么都不做。

相似题目

题目	难度	考察点
452. 用最少数量的箭引爆气球	中等	每个区间只需一个点，状态退化为记住最后一支箭的位置，是本题 $k=1$ 的形态
435. 无重叠区间	中等	目标是删最少区间使两两不交，同样按右端点排序但决策是「保留还是丢弃」
1024. 视频拼接	中等	求最少区间覆盖整条线段，按左端点分组后贪心跳最远右端点
763. 划分字母区间	中等	先扫出每个字母的最远位置再合并，贪心对象是切分点而非放置点
1288. 删除被覆盖区间	中等	判定的是包含关系，排序时右端点要降序，同键次序的作用与本题正好相反
45. 跳跃游戏 II	中等	一维贪心的另一形态，维护「当前层最远可达」而非已放点，同样靠取最右取胜
621. 任务调度器	中等	贪心结论需要构造性论证而非交换论证，训练的是同一种「证明贪心」的能力
56. 合并区间	中等	排序驱动的区间处理入门题，按左端点排序即可，可用来对照本题为何必须按右端点