JZX轻语：简
LeetCode 1353 - 最多可以参加的会议数目
发表于2024年08月30日
会议安排问题往往都能尝试使用贪心解决。考虑以下策略：首先按开始时间排序，然后每天选择有效的会议中结束时间最早的那个会议参加。所谓的有效会议是指开始时间小于等于当前时间的会议。为了实现这个策略，我们可以使用一个小顶堆，每次将已经开始的有效会议加入堆中，然后从堆中取出结束时间最早的会议参加。
如果实现时间的推进呢？我们可以使用一个cur_time变量记录当前时间，初始值为第一个会议的开始时间。然后每次从堆中取出会议参加后，如果堆为空，说明当前没有剩余的会议可以后面开的了，那么我们就将cur_time更新为下一个会议的开始时间；否则，我们将cur_time加一，表示时间推进一天。
此外，还需要注意堆中已经结束的会议需要及时清除，因为这些会议已经无法参加了。
C++的做法：
class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(), [](const auto &a, const auto &b) { return a[0] < b[0]; });
// 小顶堆
auto cmp = [](const auto& a, const auto &b) { return a[1] > b[1]; };
priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
int idx = 0, cur_time = events[0][0], ans = 0;
while (idx < events.size() || !pq.empty()) {
// 首先检查当天是否有会议开始, 若有则加入堆中
while (idx < events.size() && events[idx][0] == cur_time) {
pq.push(events[idx++]);
}
// 清除已经结束的会议(由于是按结束时间维护的小顶堆，能保证取出来的会议是最早结束的)
while (!pq.empty() && pq.top()[1] < cur_time) pq.pop();
// 从堆中取出一个会议参加
if (!pq.empty()) {
pq.pop();
++ans;
}
// 若堆为空，说明当前没有会议可以参加，更新时间为下一个会议的开始时间
if (pq.empty() && idx < events.size()) cur_time = events[idx][0];
else ++cur_time; // 否则时间直接推进一天
}
return ans;
}
};Python的做法：
import heapq
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
cand_pq = []
events.sort(key=lambda item: item[0])
cur_time = events[0][0]
cur_idx = 0
ans = 0
while cur_idx < len(events) or cand_pq:
while cur_idx < len(events) and cur_time == events[cur_idx][0]:
heapq.heappush(cand_pq, (events[cur_idx][1], events[cur_idx][0]))
cur_idx += 1
while cand_pq and cand_pq[0][0] < cur_time:
heapq.heappop(cand_pq)
if cand_pq:
ans += 1
heapq.heappop(cand_pq)
if not cand_pq:
if cur_idx < len(events):
cur_time = events[cur_idx][0]
else:
cur_time += 1
return ans