1353. 最多可以参加的会议数目
题目描述
输入数组 events，events[i] = [startDayi, endDayi] 表示第 i 个会议可以在满足 startDayi <= d <= endDayi 的任意一天 d 参加，参加只需一天。
同一天最多只能参加一个会议。返回最多能参加多少个会议。
示例 1
输入：events = [[1,2],[2,3],[3,4]] 输出：3
解释：第 1、2、3 天分别参加三个会议。
示例 2
输入：events = [[1,2],[2,3],[3,4],[1,2]] 输出：4
解释：两个 [1,2] 安排在第 1、2 天，另两个安排在第 3、4 天。
数据范围
1 <= events.length <= 10^5events[i].length == 21 <= startDayi <= endDayi <= 10^5
解题思路：按开始时间排序 + 小顶堆贪心
按天推进。每天把当天开始的会议的结束日放进小顶堆，再丢掉堆中已过期（end < day）的会议。然后参加堆顶那个会议——在所有当前可参加的会议里它最先结束，最“赶时间”，其余的以后还有机会。堆为空时直接跳到下一个会议的开始日，避免逐天空转。
为什么正确
每天选择时，堆中恰好是已开始、未结束、未参加的会议；参加结束日最早的一个不会让答案变差（交换论证）。
复杂度分析
时间 O(n log n)（排序与堆操作，天数不超过会议数加上跳跃次数），空间 O(n)。
易错点
只按结束日排序后贪心选“最早可用的一天”需要额外的并查集或集合；用堆时必须先弹出已过期的会议，否则会参加一个已经结束的会。天数可达 10^5，堆空时要跳天。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
events.sort()
heap = []
i = ans = 0
n = len(events)
day = 1
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 ansclass Solution {
public int maxEvents(int[][] events) {
Arrays.sort(events, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
PriorityQueue<Integer> heap = new PriorityQueue<>();
int i = 0, ans = 0;
int n = events.length;
int day = 1;
while (i < n || !heap.isEmpty()) {
if (heap.isEmpty()) {
day = Math.max(day, events[i][0]);
}
while (i < n && events[i][0] <= day) {
heap.offer(events[i][1]);
i++;
}
while (!heap.isEmpty() && heap.peek() < day) {
heap.poll();
}
if (!heap.isEmpty()) {
heap.poll();
ans++;
}
day++;
}
return ans;
}
}class Solution {
public:
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end());
priority_queue<int, vector<int>, greater<int>> heap;
int i = 0, ans = 0;
int n = events.size();
int day = 1;
while (i < n || !heap.empty()) {
if (heap.empty()) {
day = max(day, events[i][0]);
}
while (i < n && events[i][0] <= day) {
heap.push(events[i][1]);
i++;
}
while (!heap.empty() && heap.top() < day) {
heap.pop();
}
if (!heap.empty()) {
heap.pop();
ans++;
}
day++;
}
return ans;
}
};type minHeap []int
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(v any) { *h = append(*h, v.(int)) }
func (h *minHeap) Pop() any { old := *h; v := old[len(old)-1]; *h = old[:len(old)-1]; return v }
func maxEvents(events [][]int) int {
sort.Slice(events, func(a, b int) bool {
if events[a][0] != events[b][0] {
return events[a][0] < events[b][0]
}
return events[a][1] < events[b][1]
})
h := &minHeap{}
i, ans := 0, 0
n := len(events)
day := 1
for i < n || h.Len() > 0 {
if h.Len() == 0 {
day = max(day, events[i][0])
}
for i < n && events[i][0] <= day {
heap.Push(h, events[i][1])
i++
}
for h.Len() > 0 && (*h)[0] < day {
heap.Pop(h)
}
if h.Len() > 0 {
heap.Pop(h)
ans++
}
day++
}
return ans
}const heappush = (h, e) => {
h.push(e);
for (let i = h.length - 1, p; i > 0 && h[p = (i - 1) >> 1] > h[i]; i = p) [h[p], h[i]] = [h[i], h[p]];
};
const heappop = h => {
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
};
var maxEvents = function(events) {
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const heap = [];
let i = 0, ans = 0;
const n = events.length;
let day = 1;
while (i < n || heap.length) {
if (!heap.length) {
day = Math.max(day, events[i][0]);
}
while (i < n && events[i][0] <= day) {
heappush(heap, events[i][1]);
i++;
}
while (heap.length && heap[0] < day) {
heappop(heap);
}
if (heap.length) {
heappop(heap);
ans++;
}
day++;
}
return ans;
};const heappush = (h: number[], e: number): void => {
h.push(e);
for (let i = h.length - 1, p; i > 0 && h[p = (i - 1) >> 1] > h[i]; i = p) [h[p], h[i]] = [h[i], h[p]];
};
const heappop = (h: number[]): number => {
const top = h[0], last = h.pop()!;
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < h.length && h[l] < h[s]) s = l;
if (r < h.length && h[r] < h[s]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
};
function maxEvents(events: number[][]): number {
events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const heap: number[] = [];
let i = 0, ans = 0;
const n = events.length;
let day = 1;
while (i < n || heap.length) {
if (!heap.length) {
day = Math.max(day, events[i][0]);
}
while (i < n && events[i][0] <= day) {
heappush(heap, events[i][1]);
i++;
}
while (heap.length && heap[0] < day) {
heappop(heap);
}
if (heap.length) {
heappop(heap);
ans++;
}
day++;
}
return ans;
}其他解法
堆方法按天推进，每天从已开始的会议中选结束最早的；并查集方法按会议推进，每个会议直接跳到最早的空闲日。两者都基于“结束早的先安排”，只是一个按时间扫、一个按会议扫。
解法 2：按结束时间排序 + 并查集找空闲日 时间 O(n log n + D·α(D))，D 为最大日期，空间 O(D)
同样是“结束早的会议优先安排”的贪心，但换一个方向实现：把会议按结束时间从小到大排序，每个会议安排在不早于开始日的最早空闲日，如果这一天不超过结束日就参加。用并查集维护“从某天起的第一个空闲日”：nxt[d] 初始指向自己；某天被占用后令 nxt[d] = d + 1，find 时沿着指针跳并做路径压缩，就能快速跳过一段连续已占用的日子。
不需要按天模拟，也不需要堆，适合日期范围不太大的情况。需要开一个与最大日期等长的数组，日期范围很大时要先做离散化。
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
events.sort(key=lambda e: e[1])
last = max(e[1] for e in events)
nxt = list(range(last + 2))
def find(x):
root = x
while nxt[root] != root:
root = nxt[root]
while nxt[x] != root:
nxt[x], x = root, nxt[x]
return root
ans = 0
for s, e in events:
d = find(s)
if d <= e:
ans += 1
nxt[d] = d + 1
return ansclass Solution {
int[] nxt;
int find(int x) {
int root = x;
while (nxt[root] != root) root = nxt[root];
while (nxt[x] != root) {
int t = nxt[x];
nxt[x] = root;
x = t;
}
return root;
}
public int maxEvents(int[][] events) {
Arrays.sort(events, (a, b) -> Integer.compare(a[1], b[1]));
int last = 0;
for (int[] e : events) last = Math.max(last, e[1]);
nxt = new int[last + 2];
for (int i = 0; i <= last + 1; i++) nxt[i] = i;
int ans = 0;
for (int[] e : events) {
int d = find(e[0]);
if (d <= e[1]) {
ans++;
nxt[d] = d + 1;
}
}
return ans;
}
}class Solution {
public:
vector<int> nxt;
int find(int x) {
int root = x;
while (nxt[root] != root) root = nxt[root];
while (nxt[x] != root) {
int t = nxt[x];
nxt[x] = root;
x = t;
}
return root;
}
int maxEvents(vector<vector<int>>& events) {
sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
int last = 0;
for (auto& e : events) last = max(last, e[1]);
nxt.resize(last + 2);
for (int i = 0; i <= last + 1; i++) nxt[i] = i;
int ans = 0;
for (auto& e : events) {
int d = find(e[0]);
if (d <= e[1]) {
ans++;
nxt[d] = d + 1;
}
}
return ans;
}
};func maxEvents(events [][]int) int {
sort.Slice(events, func(i, j int) bool { return events[i][1] < events[j][1] })
last := 0
for _, e := range events {
last = max(last, e[1])
}
nxt := make([]int, last+2)
for i := range nxt {
nxt[i] = i
}
find := func(x int) int {
root := x
for nxt[root] != root {
root = nxt[root]
}
for nxt[x] != root {
nxt[x], x = root, nxt[x]
}
return root
}
ans := 0
for _, e := range events {
d := find(e[0])
if d <= e[1] {
ans++
nxt[d] = d + 1
}
}
return ans
}var maxEvents = function(events) {
events.sort((a, b) => a[1] - b[1]);
let last = 0;
for (const e of events) last = Math.max(last, e[1]);
const nxt = Array.from({ length: last + 2 }, (_, i) => i);
const find = (x) => {
let root = x;
while (nxt[root] !== root) root = nxt[root];
while (nxt[x] !== root) {
const t = nxt[x];
nxt[x] = root;
x = t;
}
return root;
};
let ans = 0;
for (const [s, e] of events) {
const d = find(s);
if (d <= e) {
ans++;
nxt[d] = d + 1;
}
}
return ans;
};function maxEvents(events: number[][]): number {
events.sort((a, b) => a[1] - b[1]);
let last = 0;
for (const e of events) last = Math.max(last, e[1]);
const nxt = Array.from({ length: last + 2 }, (_, i) => i);
const find = (x: number): number => {
let root = x;
while (nxt[root] !== root) root = nxt[root];
while (nxt[x] !== root) {
const t = nxt[x];
nxt[x] = root;
x = t;
}
return root;
};
let ans = 0;
for (const [s, e] of events) {
const d = find(s);
if (d <= e) {
ans++;
nxt[d] = d + 1;
}
}
return ans;
}