【贪心】区间选点

题目

905. 区间选点 - AcWing题库

---

给定 $N$ 个闭区间 $[a_i,b_i]$ ，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式

第一行包含整数 $N$ ，表示区间数。

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

输出格式

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

数据范围

$1 \le N \le 10^5$ ,
$-10^9 \le a_i \le b_i \le 10^9$

输入样例：

3
-1 1
2 4
3 5

输出样例：

2

解题

方法一：贪心算法

思路

贪心策略

1. 按照右端点进行升序排序。
2. 首先选择第一个区间的右端点（局部最优）。
3. 然后从前往后依次枚举每个区间：
   • 如果当前区间的左端点小于等于之前选点，说明该区间一定包含之前的选点（因为按照右端点排序，且之前的选点一定是之前某个区间的右端点，那么当前区间的右端点一定大于之前的选点），直接跳过。
   • 否则就必须在该区间上选择一个点，选择当前区间的右端点。

证明

设题目要求的最优策略选出的点数为 $ans$，而我们的贪心策略选出的点数为 $cnt$。

1. 按照上面的贪心策略来选点，如果某个区间没有点那一定会在该区间上选择一个新点，也就是说每个区间一定会包含一个点，那么这个选点的方案一定是一组合法方案， 而该题点最优策略是所有合法方案中的最小值，那么一定有 $ans \le cnt$。
2. 按照贪心策略每次新选出来点时，当前区间一定在上一个选点时的区间右边且与其无交集的那么我们选择 $cnt$ 个点的同时就找到了$cnt$ 个区间，它们互无交集，而要覆盖这些区间（合法方案的最基本要求）就至少需要 $cnt$ 个点，那么一定有 $ans \ge cnt$。

可推出 $ans = cnt$。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        int[][] segs = new int[n][2];
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            segs[i][0] = (int) in.nval;
            in.nextToken();
            segs[i][1] = (int) in.nval;
        }
        Arrays.sort(segs, (a, b) -> a[1] - b[1]);
        int ed = segs[0][1], ans = n;
        for (int i = 1; i < n; ++i) {
            if (segs[i][0] <= ed) --ans;
            else ed = segs[i][1];
        }
        System.out.println(ans);
    }
}

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 2e9;
int n;
PII segs[N];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d %d", &segs[i].first, &segs[i].second);
    sort(segs, segs + n, [](PII& a, PII& b) { return a.second < b.second; });
    int ed = segs[0].second, ans = n;
    for (int i = 1; i < n; ++i) {
        PII& seg = segs[i];
        if (seg.first <= ed) --ans;
        else ed = seg.second;
    }
    printf("%d\n", ans);
    
    return 0;
}