算法题（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 / 线段覆盖 - 洛谷