LeetCode 1353. 最多可以参加的会议数目

约 6 分钟
文章信息 7 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 华为
标签
数组 排序 贪心 堆（优先队列）

题目描述

✅ 1353. 最多可以参加的会议数目

image-20260928234334796

image-20260928234334797

image-20260928234334798

题意分析

每场会议只需选择开始日到结束日之间的一天参加，两个端点当天都可以。每天最多参加一场，每场也只能计数一次，求最多能参加多少场；参加会议不会占用它的整个起止区间。

解法：排序 + 最早结束优先

核心思路

[!blue]

按天考虑选择：尚未开始的会议今天不能参加，已经结束的会议也不能参加。对今天仍可参加的会议，应优先选结束最早的一场，因为它留给以后的机会最少。

这个选择可以用交换证明。设结束最早的候选为 A，而某个最优安排今天参加 B。若 A 没被安排，直接把今天的 B 换成 A，场数不变；若 A 被安排在未来某天，就交换两场的日期。B 今天已经开始，结束日又不早于 A，因此 B 在原先安排 A 的那天仍然可参加，交换后仍然合法。如果最优安排今天空闲，也能把 A 从以后移到今天，或直接补入 A，不会减少场数。所以总存在一个最优安排与今天的贪心选择一致。

为快速维护每天的候选，先按开始日排序，用 index 指向尚未入堆的第一场会议。小根堆 endDays 保存已开始、尚未参加的会议结束日；清除结束日小于 day 的过期会议后，堆顶就是今天最应该参加的会议。

每参加一场就把它移出堆，答案加一，日期推进一天。堆为空时没有候选，直接跳到下一场尚未处理会议的开始日，无需逐天经过空档。所有会议都处理完且堆为空时结束。

解题步骤

  1. 按开始日排序，初始化日期 day、未入堆下标 index 和答案 answer。
  2. 只要还有未入堆会议或堆非空，就继续处理。若堆为空，把日期推进到下一场会议的开始日，且不能让日期倒退。
  3. 把所有开始日不晚于 day 的会议结束日加入堆，并推进 index。
  4. 移除堆中结束日严格小于 day 的会议，结束日等于今天的仍可参加。
  5. 若堆非空，取出堆顶参加，答案加一，day 加一；否则下一轮再跳到未来的开始日。

循环仍在运行而堆为空时，必然还有未入堆的会议，所以读取 events[index] 是安全的。若最后只剩过期会议，清空堆后下一轮会直接结束，不需要额外推进日期。

代码实现

class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> endDays = new PriorityQueue<>();

        int day = 0;
        int index = 0;
        int answer = 0;

        while (index < events.length || !endDays.isEmpty()) {
            // 没有当前候选时跳到下一开始日，不逐天空转
            if (endDays.isEmpty()) {
                day = Math.max(day, events[index][0]);
            }

            while (index < events.length && events[index][0] <= day) {
                endDays.offer(events[index][1]);
                index++;
            }

            // 结束当天仍可参加，只清除严格早于今天的项
            while (!endDays.isEmpty() && endDays.peek() < day) {
                endDays.poll();
            }

            if (!endDays.isEmpty()) {
                endDays.poll();
                answer++;
                day++;
            }
        }

        return answer;
    }
}

import (
    "container/heap"
    "sort"
)

type intHeap []int

func (h intHeap) Len() int { return len(h) }

func (h intHeap) Less(i, j int) bool { return h[i] < h[j] }

func (h intHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *intHeap) Push(value any) { *h = append(*h, value.(int)) }

func (h *intHeap) Pop() any {
    old := *h
    value := old[len(old)-1]
    *h = old[:len(old)-1]
    return value
}

func maxEvents(events [][]int) int {
    sort.Slice(events, func(i, j int) bool {
        return events[i][0] < events[j][0]
    })

    endDays := &intHeap{}
    day, index, answer := 0, 0, 0

    for index < len(events) || endDays.Len() > 0 {
        // 没有当前候选时跳到下一开始日，不逐天空转
        if endDays.Len() == 0 && day < events[index][0] {
            day = events[index][0]
        }

        for index < len(events) && events[index][0] <= day {
            heap.Push(endDays, events[index][1])
            index++
        }
        // 结束当天仍可参加，只清除严格早于今天的项
        for endDays.Len() > 0 && (*endDays)[0] < day {
            heap.Pop(endDays)
        }

        if endDays.Len() > 0 {
            heap.Pop(endDays)
            answer++
            day++
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n\log n)$，排序需要 $O(n\log n)$，每场会议只入堆、出堆各一次；无会议的日期直接跳过。
  • 空间复杂度：$O(n)$，保存候选堆及排序辅助数据。

关键点总结

[!green]

  • 选择范围是今天已开始且未过期的会议，优先参加其中结束最早的一场。
  • 交换日期不会减少总场数，保证每天的局部选择能延伸成一个最优安排。
  • 排序负责按开始日加入候选，小根堆负责按结束日选候选。
  • 堆空时跳到下一个开始日，使运行时间不依赖日期跨度。

易错点总结

[!yellow]

  • 未补入今天开始的会议就选择，可能漏掉更紧迫候选。
  • 清理过期项必须使用 end < day，写成 end <= day 会错过结束当天的合法机会。
  • 优先选最晚结束的会议，可能让即将结束的会议失去最后一个可用日期。
  • 一次参加后只推进一天，不能直接跳到该会议的结束日，因为参加它只占用当天。

相似题目

题目 难度 关联与区别
1705. 吃苹果的最大数目 中等 同样每天处理一个可用对象并优先选择最早过期者，最小堆保存即将失效的候选。
630. 课程表 III 困难 原题课程持续时间不同，不能简单每天选择一个事件，本题每场只占用一天。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/90498129
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！