发表于 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

• LC 题目链接