Acwing908 区间分组

贪心

#include <bits/stdc++.h>
using namespace std;
#define N 100010
int n;

struct Range{
    int l,r;
    bool operator<(Range& w){
        return l<w.l;
    }
}range[N];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>range[i].l>>range[i].r;
    }
    sort(range+1,range+n+1);
    priority_queue<int,vector<int>,greater<int>> q;
    for(int i=1;i<=n;i++){
        auto w = range[i];
        if(q.empty() || q.top()>=w.l) q.push(w.r);
        else{
            q.pop();
            q.push(w.r);
        }
    }
    cout<<q.size()<<endl;

    return 0;
}
全部评论

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
正义执行官:人家能回你就不错了,自己不主动去问,等着天上掉馅饼,想啥呢哥们
点赞 评论 收藏
分享
05-30 12:03
山西大学 C++
offer来了我跪着...:不是骗子,等到测评那一步就知道为啥这么高工资了
点赞 评论 收藏
分享
07-07 10:44
青岛工学院 Java
机械打工仔:对方没做错任何事,你自己在这自找没趣呢,就算他工资不高,人家定多少薪资是人家的事,况且人家写了1~3年清清楚楚
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 11:30
仁者伍敌:kpi都懒得刷了属于是
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务