算法基础之区间选点

本文主要是介绍算法基础之区间选点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

区间选点

• 核心思想： 贪心

  • 每次只看当前的最优解

    • 将所有区间按右端点排序 从小到大遍历所有区间
    • 为了覆盖更多区间 取右端点作为选点
    • 若两区间互相没有交集 则再取点

  •   #include<iostream>#include<algorithm>using namespace std;const int N = 100010;int n;struct Range{int l,r;bool operator< (const Range &W)const{  //重载<return r < W.r;}}range[N];int main(){cin>>n;for(int i=0;i<n;i++){int l,r;cin>>l>>r;range[i] = {l,r};// cin >> range[i].l >> range[i].r; 也可以}sort(range,range+n);int res = 0,ed = -2e9;  //res为点个数 ed为当前选点的下标for(int i=0;i<n;i++)  //遍历所有区间{if(range[i].l > ed)  //左端点大于上一次取的右端点{ed = range[i].r;  //更新右端点res ++;  //个数+1}}cout<<res;}
    

​

这篇关于算法基础之区间选点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---