题目
给定 个闭区间 以及一个线段区间 ,请你选择尽量少的区间,将指定线段区间完全覆盖。
输出最少区间数,如果无法完全覆盖则输出 。
输入格式
第一行包含两个整数 和 ,表示给定线段区间的两个端点。
第二行包含整数 ,表示给定区间数。
接下来 行,每行包含两个整数 ,表示一个区间的两个端点。
输出格式
输出一个整数,表示所需最少区间数。
如果无解,则输出 。
数据范围
,
,
输入样例:
1 5
3
-1 3
2 4
3 5
输出样例:
2
解题
方法一:贪心算法
思路
贪心策略
- 按照左端点升序排序。
- 从前往后枚举每个区间:
- 在所有能覆盖端点 的区间中选择右端点最大的区间。
- 如果不存在能覆盖 的区间就说明无法完全覆盖,输出 结束程序。
- 如果存在就将 更新为该区间右端点的最大值。
- 如果该区间右端点大于等于端点 ,则说明已完全覆盖 ,提前跳出枚举并输出用到的区间数。
- 在所有能覆盖端点 的区间中选择右端点最大的区间。
证明
设题目要求的最优策略所需最少区间数为 ,而我们的贪心策略用到的区间数为 。
- 首先按照上面的贪心策略得到的区间数一定是一个合法解,故有 。
- 如果存在 ,因为求 时把区间按照左端点升序排序了,且每次找的都是合法且最能向右延伸的区间,如果 比 小,那就说明 不合法,而在上面的定义中 是最小合法解,存在矛盾,故 不成立。
得证。
代码
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);
}
}
评论区