AcWing 905. 区间选点

一、题目描述

给定 ( N ) 个闭区间 ([a_i, b_i])，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。

输入格式

第一行包含整数 ( N )，表示区间数。
接下来 ( N ) 行，每行包含两个整数 ( a_i, b_i )，表示一个区间的两个端点。

输出格式

输出一个整数，表示所需的点的最小数量。

数据范围

( 1 \leq N \leq 10^5 )，( -10^9 \leq a_i \leq b_i \leq 10^9 )

输入样例

3
-1 1
2 4
3 5

输出样例

2

二、题目解读

• 每个线段上最少要选择一个点。
• 如果一个点同时出现在两个线段上，就可以节约掉一个点。
• 给 ( N ) 个区间，求最少可以选择的点数（如上例可选择两个点）。

三、解题思路

贪心问题中，区间问题通常通过排序解决，常见排序方式有：

• 按左端点排序
• 按右端点排序
• 双关键字排序（先按右端点，再按左端点）

若没有思路可通过举例尝试找规律。

关键疑问

Q：为啥要按右端点排序呢？
A：选择右端点，是想获取本个线段的最大可达位置，能获得最大的覆盖利益。

核心思路

1. 所有区间按右端点从小到大排序。
2. 遍历每一个区间，如果当前区间的左端点大于前一个区间的覆盖结束边界，则需要新增一个点，并更新覆盖结束边界为当前区间的右端点。

四、实现代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n;         // 线段数量
int res;       // 结果
int ed = -INF; // 当前覆盖区间的结束边界，即右端点位置

// 结构体
struct Node {
    int l, r;
    // 按每个区间的右端点从小到大排序
    const bool operator<(const Node &b) const {
        return r < b.r;
    }
} range[N];

int main() {
    cin >> n;
    // 注意这里的数组下标是从0开始的
    for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r;

    // 右端点从小到大排序
    sort(range, range + n);

    // 遍历区间，贪心选点
    for (int i = 0; i < n; i++)
        if (range[i].l > ed) {
            res++;
            ed = range[i].r;
        }
    cout << res << endl;
    return 0;
}

五、贪心思路证明

要理解证明，需先明确 ( cnt ) 的含义：

1. 按区间右端点从小到大排序后，从前往后枚举各区间。若当前区间已包含之前选中的右端点，则跳过；否则选择当前区间的右端点，( cnt ) 即为该贪心思路选出的点的数量。
2. 所有区间中一定存在 ( cnt ) 个两两无交集的区间（因每个选中的右端点对应的区间，均未被前一个选中区间的右端点覆盖）。

证明步骤

假设最优解为 ( ans )，贪心思路选出的点数为 ( cnt )，需证明 ( ans == cnt )，等价于证明 ( ans \geq cnt ) 且 ( ans \leq cnt )。

1. 贪心思路选出的 ( cnt ) 个点是可行方案（覆盖所有区间），而 ( ans ) 是所有可行方案的最小值，故 ( ans \leq cnt )。
2. 由于存在 ( cnt ) 个两两无交集的区间，至少需要 ( cnt ) 个点才能覆盖这些区间，且需覆盖所有其他区间，故 ( ans \geq cnt )。

综上，( ans == cnt )，贪心思路最优。

类似题目

LeetCode 452. 用最少数量的箭引爆气球

一、题目描述

有一些球形气球贴在 XY 平面的墙面上，气球记录在整数数组 points 中，points[i] = [x_start, x_end] 表示气球水平直径的起始和结束坐标。一支弓箭沿 x 轴垂直射出，在坐标 x 处射出后，所有满足 x_start ≤ x ≤ x_end 的气球都会被引爆。求引爆所有气球所需的最小弓箭数。

示例

• 示例 1：
  输入：points = [[10,16],[2,8],[1,6],[7,12]]
  输出：2
  解释：在 x=6 处射一箭击破 [2,8] 和 [1,6]，在 x=11 处射一箭击破 [10,16] 和 [7,12]。
• 示例 2：
  输入：points = [[1,2],[3,4],[5,6],[7,8]]
  输出：4
  解释：无重叠区间，每个气球需单独一箭。
• 示例 3：
  输入：points = [[1,2],[2,3],[3,4],[4,5]]
  输出：2
  解释：在 x=2 处射一箭击破 [1,2] 和 [2,3]，在 x=4 处射一箭击破 [3,4] 和 [4,5]。

提示

• 1 ≤ points.length ≤ 10^5
• points[i].length == 2
• -2^31 ≤ x_start < x_end ≤ 2^31 - 1

二、解题思路

核心思想：贪心算法

这道题本质是「区间重叠问题」，核心思路与「区间选点」一致——通过排序让重叠区间聚集，再贪心选择最优射击点，最大化单次射击的覆盖范围。

具体步骤

1. 排序区间：按气球区间的「右端点」升序排序。选择右端点排序是关键，因为射击点选在右端点时，能最大程度覆盖后续可能重叠的区间，减少弓箭数量。

为什么按右端点排序？

假设区间按右端点排序后为 [1,6]、[2,8]、[7,12]、[10,16]：

• 射击点选 6，能覆盖前两个区间；
• 下一个区间 [7,12] 左端点 7 > 6，需新增射击点 12，覆盖后两个区间；
• 若按左端点排序，可能会导致射击点选择过早，无法覆盖更多区间，从而增加弓箭数。

三、Java 代码实现

class Solution {
    public int findMinArrowShots(int[][] intervals) {
        if (intervals.length == 0)
            return 0;
        // 按区间结束时间排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 1;
        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] > end) {
                count++;
                end = intervals[i][1];
            }
        }
        return count;
    }
}

代码说明

1. 排序优化：用 Long.compare(a[1], b[1]) 替代 a[1]-b[1]，避免因 x_end 接近 2^31-1 导致的整数溢出。
2. 数据类型：lastShot 用 long 存储，同样是为了防止溢出。
3. 时间复杂度：O(n log n)，核心开销在排序（n 为气球数量），遍历仅需 O(n)。
4. 空间复杂度：O(log n)，排序所需的递归栈空间（Java 内置排序为双轴快排）。

四、注意事项

1. 区间端点重叠：如示例 3 中 [1,2] 和 [2,3]，射击点选 2 可同时覆盖，符合题目中「x_start ≤ x ≤ x_end」的条件。
2. 溢出问题：题目中 x_end 可能达到 2^31-1，直接用 int 相减比较会溢出，必须用包装类或转换为 long 比较。
3. 空输入处理：当 points 为 null 或长度为 0 时，直接返回 0。

五、总结

这道题的核心是利用贪心算法，通过「按右端点排序 + 贪心选射击点」的策略，实现最小弓箭数。关键在于理解「选择右端点作为射击点」能最大化覆盖后续区间，从而减少弓箭数量。该思路同样适用于「区间选点」等类似问题，掌握后可举一反三。

要不要我帮你整理一份同类区间贪心问题汇总，包含题目链接、核心思路和代码模板？