acwing 803. 区间合并

题目链接
一个很简单的贪心，类似于线段覆盖
题意就是给出一些线段，有重复的算一条线段，问你最少有几条线段
先将线段按左端点排序，左端点相同的按右端点排序
贪心很好想，就不证明了
感觉有点像尺取法

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, ans;
struct node {
	int l, r;
	bool operator < (const node &t) const { return l < t.l || (l == t.l && r < t.r); }
} a[MAXN];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i].l, &a[i].r);
	sort(a + 1, a + n + 1);
	for (int i = 1, j = 1; i <= n; ) {
		int maxr = a[i].r;
		while (a[j].l <= maxr && j <= n) ++j, maxr = max(maxr, a[j - 1].r); //不断更新右端点，让更多的线段加进来
		++ans;
		i = j;
	}
	printf("%d", ans);
	return 0;
}

acwing 803. 区间合并

原文：https://www.cnblogs.com/cyyhhyyc/p/14824696.html