栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

LeetCode 1353. 最多可以参加的会议数目***

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LeetCode 1353. 最多可以参加的会议数目***

具体思路:

用普通区间思路没法做,但是涉及到区间贪心问题;

优先选择结束时早的,就可以腾出来时间给其他会议;

因此可以按照时间轴遍历,把所有会议加入到时间轴中;

pq保留所有已开始会议的结束时间;

每遍历一个时间点,做两件事:

  1. 删除所有的已经超时会议;
  2. 选取一个最早结束的会议参加,参加会议+1;

pq相当于保存已开始但是未结束的会议;

具体代码:
class Solution {
public:
    int maxEvents(vector>& events) {
        const int size=1e5+5;
        vector>time(size);
        int ret=0;
        priority_queue, greater<>>pq;
        int index=0;
        for(auto& vec:events){
            time[vec[0]].push_back(index);
            index++;
        }
        for(int i=0;i
            for(auto& ele:time[i]){
                pq.push(events[ele][1]);
                //加入终止时间;
            }
            while(!pq.empty()&&pq.top()
                pq.pop();
                //排除掉已经结束的会议;
            }
            if(!pq.empty()){
                ret++;
                pq.pop();
            }
        }
        return ret;
    }
};
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/947876.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号