区间覆盖问题

1. 题面

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

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

输入格式

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

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

接下来 N 行，每行包含两个整数 $[a_i,b_i]$ ，表示一个区间的两个端点。
输入样例：

1 5
3
-1 3
2 4
3 5

输出样例：

2

2. 简单分析

这道题的贪心还是非常直观的。

1. 将区间按从左到右的顺序排序
2. 每次选择能够覆盖给定区间起点的区间中，右端点最远的区间。
3. 将起点更新为该区间的右端点。
4. 回到2进行循环，直到右端点超过区间终点。

很简单的思路。但是实现的时候出了好几个bug，所以记录一下。

3. 代码解答

#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;struct Range {int l, r;bool operator< (const Range& rg)const {return l < rg.l;}
}ranges[N];int main() {int n, a, b;cin >> a >> b >> n;for (int i = 0; i < n; i ++ ) cin >> ranges[i].l >> ranges[i].r;sort(ranges, ranges + n);int res = 0;for (int i = 0; i < n; i ++ ) {int j = i, m = -2e9;  // m 为区间右端点最大值while (j < n && ranges[j].l <= a) {m = max(m, ranges[j].r);j ++;}if (m < a) {break;}res ++;a = m;i = j - 1;if (m >= b) {cout << res;return 0;}}cout << -1;return 0;
}

import java.util.*;class Range implements Comparable<Range> {int l, r;public Range(int l, int r) {this.l = l;this.r = r;}public int compareTo(Range rg) {return Integer.compare(this.l, rg.l);}
}public class Main {public static void main(String[] args) {int N = 100010;Range[] ranges = new Range[N];Scanner sc = new Scanner(System.in);int a = sc.nextInt(), b = sc.nextInt(), n = sc.nextInt();for (int i = 0; i < n; i ++ ) {int l = sc.nextInt(), r = sc.nextInt();ranges[i] = new Range(l, r);}Arrays.sort(ranges, 0, n);int res = 0;for (int i = 0; i < n; i ++ ) {int j = i, m = -0x3f3f3f3f;while (j < n && ranges[j].l <= a) {m = Math.max(ranges[j].r, m);j ++;}if (m < a) break;res ++;a = m;i = j - 1;if (m >= b) {System.out.println(res);return;}}System.out.println(-1);}
}

4. TLE的2点可能

1. 将区间右端点的最大值设置为外部变量了。
   以下面我的代码来说：不能将m设置为for循环外部变量,如果设置为外部变量仍需要在循环内每次赋新值，否则，当所给区间不能覆盖中间某区域时，while循环体不会执行，那么 j = i，i = i- 1，就会陷入循环。
2. 手误，将while循环中的 j 写为 i 了。同样的会发生 j 不更新问题。j = i，i = i- 1，就会陷入循环。