AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 吐槽
  • App
  • 登录/注册

AcWing 906. 区间分组

作者: 作者的头像   黎虽无意逐鹿 ,  2022-11-21 18:26:23 ,  所有人可见 ,  阅读 15


0


区间分组问题
1.将所有区间按照左端点从小到大排序
2.从前往后依次遍历每个区间:
判断能否将其放到某个现有的组中(当前区间左端点L[i] <= MAN_r)
2.1如果不存在这样的组,就开一个新的组,然后将其放入新组中
2.2如果存在这样的组,就将其放入组中,更新当前组的Max_r 为R[i]


#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 +10;
struct Range
{
    int l ,r ;
    bool operator <(const Range &W) const
    {
        return l<W.l;
    }
}range[N];
int main()
{
    int n;
    cin>>n;
    for(int i = 0 ; i < n ; i ++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        range[i] = {l,r};
    }
    //1.按照左端点从小到大排序
    sort(range,range+n);
    //2.从前往后依次遍历每个区间
    priority_queue<int,vector<int>,greater<int> >heap;
    for(int i = 0; i < n  ;i ++)
    {
        //如果不存在这样的组,就开一个新的组
        if(heap.empty()||range[i].l <= heap.top())heap.push(range[i].r);
        else//如果存在这样的组,就将其放入组中,并更新Max_r
        {
            heap.pop();
            heap.push(range[i].r);
        }
    }
    cout<<heap.size();
    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息