跳到主要内容

AcWing 905. 区间选点

本节目标

按闭区间右端点升序选点，用最少点覆盖全部区间。

这是区间排序与调度中“最早结束优先”的闭区间母题。

查看 AcWing 原题

题意与约束​

给定若干闭区间 [l,r]，选择尽可能少的数轴点，使每个区间至少包含一个被选点。空集合不需要选点；端点被包含，所以点 r 能覆盖右端点等于 r 的区间。

直接思路与瓶颈​

可以枚举所有可能的选点集合再检查覆盖，但数轴坐标范围和组合数量都可能很大。也不能每遇到未覆盖区间就任意选左端点：这会缩小对后续区间的兼容范围。

贪心模型与算法推导​

将区间按右端点从小到大排序。维护最近一次选出的点 selected：扫描到 [l,r] 时，若 selected >= l，它已落在该闭区间内；否则必须新增一点，选择当前最早结束区间的右端点 r，即在该区间内尽可能靠右地落点。空输入自然返回零。

正确性依据​

考虑当前右端点最小而尚未覆盖的区间 [l,r]。任何可行解都必须在它内放一点 p。把该点替换为 r 不会损害后续区间：后续区间的右端点不小于 r，且若它原来包含 p，其左端点不大于 p <= r，故也包含 r。因此存在最优解以 r 为当前选点。选定 r 后，所有左端点不大于 r 的后续闭区间已覆盖；重复该安全选择即得到最少点数。

样例执行过程​

区间为 [1,3]、[2,4]、[5,6]，排序顺序不变。

  1. selected 尚不存在，处理 [1,3] 时选点 3。
  2. [2,4] 满足 3 >= 2，点 3 已覆盖它，不新增。
  3. [5,6] 满足 3 < 5，选点 6。

最终选点为 3,6，答案为 2。

代码实现​

C++17
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

int minPoints(vector<pair<int, int>> intervals) {
    sort(intervals.begin(), intervals.end(), [](const auto& first, const auto& second) {
        return first.second < second.second;
    });

    int count = 0;
    bool hasSelected = false;
    int selected = 0;
    for (const auto& [left, right] : intervals) {
        if (!hasSelected || selected < left) {
            selected = right;
            hasSelected = true;
            ++count;
        }
    }
    return count;
}

复杂度分析​

排序需要 O(n log n)，单次扫描 O(n)；排序副本使用 O(n) 空间。

边界与易错点​

  • 本题是闭区间，判断未覆盖必须是 selected < l，不是 <=。
  • 空区间集合返回 0。
  • 不必保存所有已选点，只需保存最后一个，因为排序后它是唯一可能覆盖当前区间的最近选择。

模式迁移​

无重叠区间可改为尽量保留右端点最小的区间；最少箭引爆气球与本题完全同构，一支箭就是一个选点。两题都复用右端点选择与上述替换论证。