(LeetCode 每日一题) 1353. 最多可以参加的会议数目 (优先队列、小顶堆)

题目：1353. 最多可以参加的会议数目

思路：优先队列实现小顶堆，0(mx*logn)
在第i天，优先选endDay最小的那一个活动进行。那么遍历每一天，用小顶堆来维护每个活动的最后一天即可，细节看注释。

C++版本：

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
    	// 找到最后一天
        int mx=events[0][1];
        for(auto x:events){
            mx=max(mx,x[1]);
        }
        // 用数组来记录每一个startDay对应的所有endDay,方便遍历的时候维护小顶堆
        vector<vector<int>> v(mx+1);
        for(auto x:events){
            v[x[0]].push_back(x[1]);
        }
		// 优先队列实现小顶堆
        priority_queue<int,vector<int>,greater<>> qu;
        // 答案
        int ans=0;
        // 遍历每一天
        for(int i=1;i<=mx;i++){
        	// 先将无法进行的活动都弹出
            while(!qu.empty()&&qu.top()<i){
                qu.pop();
            }
            // 将所有startDay==i的endDay都加入到小顶堆qu
            for(auto x:v[i]){
                qu.push(x);
            }
            // 如果队列不为空，说明当天可选一个活动进行
            // 这个活动就是最小的endDay
            if(!qu.empty()){
                ans++;
                qu.pop();
            }
        }
        return ans;
    }
};

JAVA版本：

class Solution {
    public int maxEvents(int[][] events) {
        int mx=events[0][1];
        for(var x:events){
            mx=Math.max(mx,x[1]);
        }
        List<Integer>[] v=new ArrayList[mx+1];
        Arrays.setAll(v,i-> new ArrayList<>() );
        for(var x:events){
            v[x[0]].add(x[1]);
        }

        PriorityQueue<Integer> qu =new PriorityQueue<>();
        int ans=0;
        for(int i=1;i<=mx;i++){
            while(!qu.isEmpty()&&qu.peek()<i){
                qu.poll();
            }
            for(var x:v[i]){
                qu.add(x);
            }
            if(!qu.isEmpty()){
                ans++;
                qu.poll();
            }
        }
        return ans;
    }
}