出题人题解 | #城市规划#

原题解链接：https://ac.nowcoder.com/discuss/149980

考虑一个很显然的$O(mlogm)O(m\; log\; m)$的做法

首先对所有线段按照右端点排序，然后每次在右端点处切

但是$mm$达到了$10^{7}10^7$级别，所以不能通过此题

由于题目保证所有线段的值域为$1-n1-n$，我们可以对所有左端点，直接记录出右端点最靠左的位置

同样每次切右端点，扫一遍即可

时间复杂度:$O(m)O(m)$

#include<cstdio>
const int MAXN = 1e6 + 10;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
#define min(a, b) (a < b ? a : b)
char buf[(1 << 22)], *p1 = buf, *p2 = buf;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
int r[MAXN];
int main() {
	N = read(); M = read();
	for(int i = 1; i <= N; i++) r[i] = N + 1;
	for(int i = 1; i <= M; i++) {
		int x = read(), y = read();
		r[x] = min(y, r[x]);
	}
	int cur = N + 1, ans = 0;
	for(int i = 1; i <= N; i++) {
		cur = min(cur, r[i]);
		if(i == cur) cur = r[i], ans++;
	}
	printf("%d", ans);
    return 0;
}