审题本题需要我们记录不相互覆盖的最大区间个数思路方法一贪心涉及到区间的贪心题我们一般先要对区间进行排序一共分四种排序1左端点升序2右端点升序3左端点降序4右断点降序具体可以采用哪种预处理排序方法取决于题意以本题的样例为例分析我们先尝试左端点升序排序此时区间1为【0,2】区间2为【13】区间3为【2,4】。我们看到区间1和2是互相覆盖的此时我们舍弃掉区间隔2保留区间1因为保留右端点更小的区间有更大可能不与后面的区间覆盖从而得到更多的不覆盖区间。然后再用区间1和区间3进行比较发现他们不是互相覆盖所以answer遍历结束结束搜索。我们发现左端点升序可以解决该问题所以我们就采用左端点升序解题。解题#includeiostream #includealgorithm 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 / 线段覆盖 - 洛谷