Leetcode1353_最多可以参加的会议数目

zxcoder 2020-03-01 原文

题目地址
给定n个会议时间区间，会议不用全程参加，问最多能参加的数目。

时间区间按左端点排序，扫一遍，每一天把当天开始的区间结束时间加入，同时把这一天之前结束的区间删掉，然后贪心从最小堆取出结束时间的区间即可。
multiset是最小堆，priority_queue是最大堆。

code

class Solution {
public:
    
    int maxEvents(vector<vector<int>>& events) {
        int n=events.size();
        sort(events.begin(),events.end());
        //multiset从小到大 priority_queue从大到小
        multiset<int> s;
        int i=1;
        int j=0;
        int ans=0;
        while(j<n || !s.empty()){
            //把第i天开始的会议结束时间加入，从小到大排序
            while(j<n && events[j][0]==i){
                s.insert(events[j][1]);
                j++;
            }
            //把第i天之前结束的会议删掉
            while(!s.empty() && *s.begin()<i){
                s.erase(s.begin());
            }
            //如果还有可用会议，就是当前可用的结束时间最前的会议，贪心取并删除
            if(!s.empty()){
                s.erase(s.begin());
                ans++;
            }
            i++;
        }
        return ans;
    }
};