【贪心】区间覆盖

题目

907. 区间覆盖 - AcWing题库

---

给定 $N$ 个闭区间 $[a_i,b_i]$ 以及一个线段区间 $[s,t]$ ，请你选择尽量少的区间，将指定线段区间完全覆盖。

输出最少区间数，如果无法完全覆盖则输出 $-1$ 。

输入格式

第一行包含两个整数 $s$ 和 $t$ ，表示给定线段区间的两个端点。

第二行包含整数 $N$ ，表示给定区间数。

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

输出格式

输出一个整数，表示所需最少区间数。

如果无解，则输出 $-1$ 。

数据范围

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

输入样例：

1 5
3
-1 3
2 4
3 5

输出样例：

2

解题

方法一：贪心算法

思路

贪心策略

1. 按照左端点升序排序。
2. 从前往后枚举每个区间：
   • 在所有能覆盖端点 $s$ 的区间中选择右端点最大的区间。
     • 如果不存在能覆盖 $s$ 的区间就说明无法完全覆盖，输出 $-1$ 结束程序。
     • 如果存在就将 $s$ 更新为该区间右端点的最大值。
       • 如果该区间右端点大于等于端点 $t$ ，则说明已完全覆盖 $[s,t]$ ，提前跳出枚举并输出用到的区间数。

证明

设题目要求的最优策略所需最少区间数为 $ans$，而我们的贪心策略用到的区间数为 $cnt$ 。

2. 首先按照上面的贪心策略得到的区间数一定是一个合法解，故有 $ans \le cnt$ 。
3. 如果存在 $ans < cnt$，因为求 $cnt$ 时把区间按照左端点升序排序了，且每次找的都是合法且最能向右延伸的区间，如果 $ans$ 比 $cnt$ 小，那就说明 $ans$ 不合法，而在上面的定义中 $ans$ 是最小合法解，存在矛盾，故 $ans < cnt$ 不成立。

$ans = cnt$ 得证。

代码

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

public class Main {
    static final int INF = (int) 2e9;
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int s = (int) in.nval;
        in.nextToken();
        int t = (int) in.nval;
        in.nextToken();
        int n = (int) in.nval;
        int[][] segs = new int[n][2];
        int ans = 0;
        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[0] - b[0]);
        for (int i = 0; i < n; ++i) {
            int j = i, ed = -INF;
            for (; j < n && segs[j][0] <= s; ++j) ed = Math.max(ed, segs[j][1]);
            if (ed < s) break;
            ++ans;
            if (ed >= t) {
                System.out.println(ans);
                return;
            }
            s = ed;
            i = j - 1;
        }
        System.out.println(-1);
    }
}