贪心：908. 最大不相交区间数量

贪心：908. 最大不相交区间数量

 

与“905.区间选点”相同

/*贪心：每一步取最优，只有在单峰情况下局部最优才是全局最优1.将所有区间按右端点排序2.从小到大依次枚举每个区间，每个区间取最右边的值
*/#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>using namespace std;typedef pair<int, int> PII;
vector<PII> elems;const int N = 1e5 + 10;// 按照second升序排序
bool cmp(pair<int,int>a, pair<int,int>b)
{return a.second < b.second;
}int n;int main()
{cin >> n;for(int i = 0; i < n; i++){int l, r;cin >> l >> r;elems.push_back({l, r});}// 排序sort(elems.begin(), elems.end(), cmp);int res = 0, end = -2e9;for(auto e : elems){if(e.first > end){res ++;end = e.second;}}cout << res << endl;return 0;
}