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

题目描述

题目分析

(1) 为了保证能参加最多的会议，所以每一天都尽量选择一个会议参加，首先要在已经开始的会议里面挑选，先把所有开始的会议入队

(2) 检查队列中的会议，若会议结束时间已经超过今天了，则出队，说明已经来不及参加了。

(3) 接下来队列里的所有会议都是今天可以去参加的，按道理说，先把[ 早结束的会议] 参加完要好一些，因为像这样，还能在未来的某一天，在其他会议结束再前去参加 [ 后结束的会议] 。

(4) 每天都需要做 第(3) 步的判断，保证最后能参加最多的会议

综上，使用升序的优先队列，队列的值即为会议的结束时间，再此之前根据会议的开始时间进行排序，因为会议是越早开始越好安排。这体现了一种贪心思路。

class Solution {
          
   
    const int maxn = 100001;
public:
    int maxEvents(vector<vector<int>>& events) {
          
   
        vector<int> in[maxn];   // in[i] : 在第i天开始的会议的索引编号
        int idx = 0, ma = 0, ans = 0;
        for (auto &e : events) {
          
   
            in[e[0]].emplace_back(idx++);
            ma = max(ma, e[1]);
        }
        std::priority_queue<int, vector<int>, greater<int>> pq;  // 小根堆，存放会议结束天数
        for (int day = 1; day <= ma; day++) {
          
   
            for (auto idx : in[day])
                pq.emplace(events[idx][1]);    // 将会议结束时间加入
            while (!pq.empty() && pq.top() < day) pq.pop();     // 将不合法的日期移出
            if (!pq.empty() && pq.top() >= day) {
          
   
                ans++;      // 在这一天有满足条件的会议
                pq.pop();   // 计算后移出堆顶元素
            }
        }
        return ans;
    }
};

类似题目