算法题（155）：线段覆盖

审题：

本题需要我们记录不相互覆盖的最大区间个数

思路：
方法一：贪心

涉及到区间的贪心题我们一般先要对区间进行排序，一共分四种排序

1：左端点升序

2：右端点升序

3：左端点降序

4：右断点降序

具体可以采用哪种预处理排序方法取决于题意

以本题的样例为例分析：
我们先尝试左端点升序排序，此时区间1为【0,2】，区间2为【1，3】，区间3为【2,4】。我们看到区间1和2是互相覆盖的，此时我们舍弃掉区间隔2，保留区间1（因为保留右端点更小的区间有更大可能不与后面的区间覆盖，从而得到更多的不覆盖区间）。然后再用区间1和区间3进行比较，发现他们不是互相覆盖，所以answer++，遍历结束，结束搜索。

我们发现左端点升序可以解决该问题，所以我们就采用左端点升序解题。

解题：

#include<iostream> #include<algorithm> using namespace std; const int N = 1e6 + 10; struct space { int l; int r; }a[N]; int n; bool cmp(space& s1, space& s2) { return s1.l < s2.l; } int main() { //数据录入 cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].l >> a[i].r; } //左端点升序排序 sort(a + 1, a + 1 + n, cmp); //区间搜索 int answer = 1; int r = a[1].r; for (int i = 2; i <= n; i++) { int left = a[i].l; int right = a[i].r; if (left < r) { r = min(r, right); } else { answer++; r = right; } } cout << answer << endl; return 0; }

1.由于每个区间需要存储左右端点，所以我们用结构体来表示区间

2.answer初始化为1：因为不管什么情况，只要有区间，一定会有一个区间是可以单独选出来而不覆盖的（只有一个区间不存在覆盖的问题）

P1803 凌乱的yyy / 线段覆盖 - 洛谷