题目链接 Restaurant
题目意思就是在$n$个区间内选出尽可能多的区间，使得这些区间互不相交。
我们先对这$n$个区间去重。
假如有两个区间$[l1, r1]，[l2, r2]$
若满足$l1 >= l2$且 $r1 <= r2$，那么$[l2, r2]$就是可以被去掉的。
因为这两个区间里我们显然最多只能选择一个。
如果我们在答案里选择了$[l2, r2]$，那么我们如果把$[l2, r2]$换成$[l1, r1]$的话
这个答案肯定还是满足题意的。
甚至可能腾出了可以放下其他区间的空间。
那么我们去重之后进行离散化，接下来就是贪心的过程。
我们把这些处理好的区间以左端点为关键字升序排序。
排好序的区间，右端点肯定也是升序的。
我们预处理出$f[i]$为右端点小于等于$i$的所有区间的编号的最大值。
我们从最后一个区间开始选，
对于当前我们可以选择的范围肯定要选择编号更大的。
因为编号越大说明左端点越大，给其他区间留出的空间越多。
于是我们从最后一个区间开始选，依次贪心，这样就可以了。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int inf = 1e9 + 1;
const int N = 1e6 + 10;
const int A = 22; struct node{
int x, y, s, t;
friend bool operator < (const node &a, const node &b){
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
} a[N], c[N]; int b[N << 2], d[N << 2];
int cnt, tot, now;
int n, m, et;
int mx;
int st[N << 1][A];
int ans; bool cmp(const node &a, const node &b){
return a.s == b.s ? a.t > b.t : a.s < b.s;
} int main(){ scanf("%d", &n);
cnt = 0;
rep(i, 1, n){
int x, y;
scanf("%d%d", &a[i].x, &a[i].y);
a[i].s = a[i].y;
a[i].t = a[i].x + inf;
} sort(a + 1, a + n + 1, cmp); cnt = 0;
for (int i = 1, j; i <= n;){
j = i + 1;
while (j <= n && a[j].t <= a[i].t) ++j;
c[++cnt] = a[i];
i = j;
} et = 0;
rep(i, 1, cnt){
b[++et] = c[i].x;
b[++et] = c[i].y;
} rep(i, 1, et) d[i] = b[i];
sort(d + 1, d + et + 1);
tot = unique(d + 1, d + et + 1) - d - 1;
rep(i, 1, et) b[i] = lower_bound(d + 1, d + tot + 1, b[i]) - d;
et = 0;
rep(i, 1, cnt){
c[i].x = b[++et];
c[i].y = b[++et];
} mx = c[cnt].y; rep(i, 1, mx){
if (i < c[1].y) continue;
int l = 1, r = cnt;
while (l + 1 < r){
int mid = (l + r) >> 1;
if (c[mid].y <= i) l = mid;
else r = mid - 1;
} if (c[r].y <= i) st[i][0] = r;
else st[i][0] = l; } now = mx;
ans = 0;
for (; now > 0; ){
int fl = st[now][0];
if (fl == 0) break;
++ans;
now = c[fl].x - 1;
} printf("%d\n", ans);
return 0; }