给定 N 个闭区间 [ai,bi],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。
输出可选取区间的最大数量。
第一行包含整数 N,表示区间数。
接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
输出一个整数,表示可选取区间的最大数量。
1≤N≤105,
−109≤ai≤bi≤109
3 -1 1 2 4 3 5
2
/* 1.将区间按照右端点从小到大进行排序; 2.维护一下当前已经选过的区间的右端点的最大值ed,从左到右遍历每个区间, 如果当前区间的左端点大于ed,把当前区间加到已经选过的区间里面,并更新ed. 证明: 在数学中要证明A=B,有一种证明方法是证明出来"A>=B&&A<=B",因此即可证"A=B". 假设最优的方案选出的最大不相交区间的数量是ans,我们的贪心方式得出的数量是cnt, 易知我们给出的贪心方式是一种合法方案,那么由ans的定义(所有合法方案的数量的最大值)可知, ans>=cnt成立. 证明ans<=cnt: 反证法: 假如ans>cnt,那么也就存在ans个互不相交的区间,因此要选择最少的点把所有的区间都覆盖掉 至少需要ans个点,但事实上只需要cnt个点救能把所有的区间都覆盖掉,而cnt<ans,也就是说cnt 永远不会等于ans,与事实矛盾,因此ans>cnt不成立,因此ans<=cnt成立. 综上所述,"ans>=cnt&&ans<=cnt"->"ans=cnt". */ #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; struct node { int l, r; bool operator<(const node &b) const { return r < b.r; } } range[N]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> range[i].l >> range[i].r; sort(range, range + n); int res = 0, ed = -2e9; for (int i = 0; i < n; i++) { if (range[i].l > ed) { res++; ed = range[i].r; } } cout << res << endl; return 0; }