侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【贪心】区间覆盖

GabrielxD
2023-02-08 / 0 评论 / 0 点赞 / 90 阅读 / 800 字
温馨提示:
本文最后更新于 2023-02-08,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

907. 区间覆盖 - AcWing题库


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

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

输入格式

第一行包含两个整数 sstt ,表示给定线段区间的两个端点。

第二行包含整数 NN ,表示给定区间数。

接下来 NN 行,每行包含两个整数 ai,bia_i,b_i ,表示一个区间的两个端点。

输出格式

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

如果无解,则输出 1-1

数据范围

1N1051 \le N \le 10^5 ,
109aibi109-10^9 \le a_i \le b_i \le 10^9 ,
109st109-10^9 \le s \le t \le 10^9

输入样例:

1 5
3
-1 3
2 4
3 5

输出样例:

2

解题

方法一:贪心算法

思路

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

设题目要求的最优策略所需最少区间数为 ansans,而我们的贪心策略用到的区间数为 cntcnt

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

ans=cntans = 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);
    }
}
0

评论区