forked from lzl124631x/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
s1.cpp
22 lines (22 loc) · 801 Bytes
/
s1.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// OJ: https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
// Ref: https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/discuss/510263/JavaC%2B%2BPython-Priority-Queue
class Solution {
public:
int maxEvents(vector<vector<int>>& A) {
sort(A.begin(), A.end());
priority_queue<int, vector<int>, greater<int>> pq;
int N = A.size(), i = 0, day = A[0][0], ans = 0;
while (i < N || pq.size()) {
if (pq.empty()) day = A[i][0];
while (i < N && A[i][0] == day) pq.push(A[i++][1]);
pq.pop();
++ans;
++day;
while (pq.size() && pq.top() < day) pq.pop();
}
return ans;
}
};