最多可以参加的会议数目 图解题解

这道题到底在问什么

输入

events=[[1,4],[4,4],[2,2],[3,4],[1,1]]

输出

4

先想最直接的笨办法

所有会议都处理完、堆也空了。整趟下来一共参加了 4 场,和开头说的答案 4 一致。回头看:我们没有暴力枚举安排,只是「每天入堆、清过期、抢结束最早的一场」,贪心一遍就拿到最优解。（动画第 26 步）

最优解：一步一步想明白

1. 3记住这句:每天先把开始的会议结束日入堆,清掉过期的,再参加堆顶,也就是结束日最早的那场。最快过期的优先抢,这就是贪心的关键。
2. 4贪心为什么对:结束早的不抢就过期,结束晚的后面还能补。先救最快过期的,总数不会更差。
3. 5第一步:把会议按开始日从早到晚排序,排序后是 [[1,4], [1,1], [2,2], [3,4], [4,4]]。堆现在是空的,从最早的开始日往后扫每一天。
4. 6堆空了、还有会议没处理,把「今天」跳到下一场最早的开始日 day=1,从这天继续安排。
5. 7来到第 1 天。堆现在是空的,先把今天开始的会议入堆。 接下来:把开始日 ≤ 1 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。
6. 8会议1 [1,4] 的开始日 ≤ 今天 day=1,已经开了,把它的结束日 4 丢进小根堆。堆会自动把结束最早的浮到堆顶。
7. 9会议2 [1,1] 的开始日 ≤ 今天 day=1,已经开了,把它的结束日 1 丢进小根堆。堆会自动把结束最早的浮到堆顶。
8. 10今天 day=1 看堆顶:结束日 1,这是当前所有能参加的会议里结束最早的一场,就参加它。
9. 11参加完结束日 1 的那场,已参加 ans=1。今天用掉了,把「今天」推进一天到 day=2,继续处理剩下的会议。
10. 12来到第 2 天。堆里现在有 1 场候选,堆顶结束日 4。 接下来:把开始日 ≤ 2 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。
11. 13会议3 [2,2] 的开始日 ≤ 今天 day=2,已经开了,把它的结束日 2 丢进小根堆。堆会自动把结束最早的浮到堆顶。
12. 14今天 day=2 看堆顶:结束日 2,这是当前所有能参加的会议里结束最早的一场,就参加它。
13. 15参加完结束日 2 的那场,已参加 ans=2。今天用掉了,把「今天」推进一天到 day=3,继续处理剩下的会议。
14. 16来到第 3 天。堆里现在有 1 场候选,堆顶结束日 4。 接下来:把开始日 ≤ 3 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。
15. 17会议4 [3,4] 的开始日 ≤ 今天 day=3,已经开了,把它的结束日 4 丢进小根堆。堆会自动把结束最早的浮到堆顶。
16. 18今天 day=3 看堆顶:结束日 4,这是当前所有能参加的会议里结束最早的一场,就参加它。
17. 19参加完结束日 4 的那场,已参加 ans=3。今天用掉了,把「今天」推进一天到 day=4,继续处理剩下的会议。
18. 20来到第 4 天。堆里现在有 1 场候选,堆顶结束日 4。 接下来:把开始日 ≤ 4 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。
19. 21会议5 [4,4] 的开始日 ≤ 今天 day=4,已经开了,把它的结束日 4 丢进小根堆。堆会自动把结束最早的浮到堆顶。
20. 22今天 day=4 看堆顶:结束日 4,这是当前所有能参加的会议里结束最早的一场,就参加它。
21. 23参加完结束日 4 的那场,已参加 ans=4。今天用掉了,把「今天」推进一天到 day=5,继续处理剩下的会议。
22. 24来到第 5 天。堆里现在有 1 场候选,堆顶结束日 4。 接下来:把开始日 ≤ 5 的会议结束日入堆、清掉过期的、再参加堆顶结束最早的一场。
23. 25堆顶结束日 4 < 今天 day=5,这场已经过期、再也赶不上了,直接从堆里弹掉、不计入答案。
24. 26所有会议都处理完、堆也空了。整趟下来一共参加了 4 场,和开头说的答案 4 一致。回头看:我们没有暴力枚举安排,只是「每天入堆、清过期、抢结束最早的一场」,贪心一遍就拿到最优解。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
import heapq
class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort()
        heap = []
        i = 0
        day = 0
        ans = 0
        n = len(events)
        while i < n or heap:
            if not heap:
                day = max(day, events[i][0])
            while i < n and events[i][0] <= day:
                heapq.heappush(heap, events[i][1])
                i += 1
            while heap and heap[0] < day:
                heapq.heappop(heap)
            if heap:
                heapq.heappop(heap)
                ans += 1
                day += 1
        return ans

#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        priority_queue<int, vector<int>, greater<int>> pq;
        int i = 0, day = 0, ans = 0, n = events.size();
        while (i < n || !pq.empty()) {
            if (pq.empty()) day = max(day, events[i][0]);
            while (i < n && events[i][0] <= day) pq.push(events[i++][1]);
            while (!pq.empty() && pq.top() < day) pq.pop();
            if (!pq.empty()) { pq.pop(); ans++; day++; }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int i = 0, day = 0, ans = 0;
        while (i < events.length || !pq.isEmpty()) {
            if (pq.isEmpty()) day = Math.max(day, events[i][0]);
            while (i < events.length && events[i][0] <= day) pq.offer(events[i++][1]);
            while (!pq.isEmpty() && pq.peek() < day) pq.poll();
            if (!pq.isEmpty()) { pq.poll(); ans++; day++; }
        }
        return ans;
    }
}

复杂度

面试官可能追问