1353. Maximum Number of Events That Can Be Attended

问题：

给定一组event的举办起始日表，

可以参加任意event在任意天。

求最多能参加多少个event。

⚠️ 注意：同一天只能参加一个event。

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 <= startDayi <= endDayi <= 10^5

　　

example 1:

 解法：sort+minHeap （priority_queue）

思路：

• 按照start日，对event，进行排序
• 从第一个start日开始，作为开始参与的第一天curday。
  • 在今天curday中，能够参与的event，加入heap中。
    • 加入条件：start==curday的所有event。
    • 加入对象：end日。
  • 选择最早结束的event->即：heap->top 作为curday的参加event。
    • heap.pop：弹出已选择的event
    • res++：参与的event数++
    • curday++：今天度过
  • 今天度过：删除heap中今天之前结束的所有event。
    • 删除条件：end<curday

代码参考：

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int res = 0;
        priority_queue<int, vector<int>, greater<int>> pq;//end :: top:smallest
        sort(events.begin(), events.end());//sort by start <<<
        int n = events.size();
        int curday = 0;
        int evt_id = 0;
        while(!pq.empty() || evt_id<n) {
            //on curday: 
            if(pq.empty()) curday = events[evt_id][0];
            //add all start==curday events to pq
            for(evt_id; evt_id<n && events[evt_id][0]==curday; evt_id++) {
                pq.push(events[evt_id][1]);
            }
            //chose one of them (the earlist end event) to take part in.->res+1
            //then curday+1
            pq.pop();
            res++;
            curday++;
            //clean all events whose endday < curday
            while(!pq.empty() && pq.top()<curday) pq.pop();
        }
        return res;
    }
};