题解 | #参加会议的最大数目#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param meetings int整型vector<vector<>>
     * @return int整型
     */
    int attendmeetings(vector<vector<int> >& meetings) {
        // 按照开始时间排序--升序
        sort(meetings.begin(), meetings.end(), [](const vector<int>& a,
        const vector<int>& b) {
            return a[0] < b[0];
        });

        // 记录参与的会议数量
        int res = 0;

        // 表示当前第几个会议
        int curIndex = 0;

        // 当前处于第几天，开始是第一个会议的开始时间
        int curDay = meetings[0][0];

        // 小顶堆
        priority_queue<int, vector<int>, greater<int>> pq;

        // 扫描当前会议，或者小顶堆不为空
        while (curIndex < meetings.size() || !pq.empty()) {
            // 加入已经开始的会议--还未扫描到最后，且扫描的当前会议的开始时间和前面一致
            while (curIndex < meetings.size() && meetings[curIndex][0] == curDay) {
                // 把结束时间加入小顶堆
                pq.push(meetings[curIndex][1]);
                curIndex++;
            }

            // 剔除已经结束的会议
            while (!pq.empty() && pq.top() < curDay) {
                // 此时优先级队列的顶部存放的是结束时间最短的会议
                pq.pop();
            }

            // 找出结束时间最短的会议来参加
            if (!pq.empty()) {
                pq.pop();
                res++;
            }

            curDay++;
        }

        return res;
    }
    // write code here

};