1353. Maximum Number of Events That Can Be Attended

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/

Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Example 3:

Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4

Example 4:

Input: events = [[1,100000]]
Output: 1

Example 5:

Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
Output: 7

Constraints:

• 1 <= events.length <= 10^5

• events[i].length == 2

• 1 <= events[i][0] <= events[i][1] <= 10^5

一系列events有初始日期和终止日期（用int index表示），一天内最多参加一个event，问最多能参加多少个events。在同一天，greedy的优先选择event 终止时间短的参与，因为长的可以留给后面的日子来参加。对startTime做排序，然后遍历每一天d，把startTime和d相同的都放入min heap中（和meeting rooms II类似，min heap中存endTime），再将heap中endTime小于d（已过期的）的都抛出，最后根据前面greedy策略抛出endTime最靠前的作为当前日子要参与的event。

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        priority_queue<int, vector<int>, greater<int>> pq;
        int res = 0; 
        for (int i = 0, N = events.size(), d = 0; d <= 100000; ++d) {
            // push startTime == 当前day
            while (i < N && events[i][0] == d) pq.push(events[i++][1]);
            // pop endtime 小于当前day的
            while (!pq.empty() && pq.top() < d) pq.pop();
            if (!pq.empty()) {
                // 消耗掉一个endTime最前的event
                pq.pop();
                ++res;
            }
        }
        return res;
    }
};