本文主要是介绍贪心: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;
}
这篇关于贪心:908. 最大不相交区间数量的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!