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

2021-07-28 HGNULB 约 6 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

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

题意分析

每场会议给出开始日和结束日，只要在这两天之间（含两端）挑任意一天出席就算参加了这场会议。每一天最多只能出席一场会议，求最多能参加多少场。

这里最容易读错的是「参加一场会议只占用一天」，而不是要把整个区间都占满。所以这不是区间不重叠问题，而是「天」和「会议」之间的二分图匹配问题：每一天是一个容量为 1 的资源，每场会议可以匹配它区间内的任意一天。

约束信号在于天数和会议数都到 $10^5$ 量级，逐天暴力枚举可行，但每天再扫一遍所有会议就不行了，需要一个能随时间推进增量维护「当前可参加会议集合」的结构。

边界要注意：会议区间可以完全重合、可以是单点（开始日等于结束日）、时间轴上可能存在没有任何会议的空档；答案上界是会议数量，也受限于被会议覆盖的天数总量。

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

核心思路

每天至多参加一个已经开始且尚未结束的会议。若当天有多个候选，应参加结束时间最早的那个：把更早过期的机会先用掉，较晚结束的会议仍可留给之后，不会减少未来选择。

先按开始日排序，用小根堆保存所有已开始会议的结束日。每天依次完成三件事：加入开始日不晚于当天的会议、删除结束日早于当天的过期会议、弹出最小结束日并参加。若堆为空，直接把日期跳到下一个会议的开始日，避免逐天空转。

贪心正确性：设某个最优方案当天选择结束日较晚的会议 B，而算法选择结束更早的 A。把该方案当天的 B 换成 A；若方案以后安排了 A，再把那个位置换成 B。因为 B 结束得不早于 A，交换后仍合法，参加数量不变。因此总存在一个最优方案与当前选择一致。

解题步骤

按会议开始日升序排序。

当堆为空时，把 day 跳到下一个未处理会议的开始日。

将所有 start <= day 的会议结束日加入小根堆。

删除所有 end < day 的过期会议。

若堆非空，弹出结束日最早的会议，答案加一，日期加一。

直到没有未处理会议且堆为空。

例如 [[1,2],[1,2],[2,3]]：第 1、2 天依次参加两个结束日为 2 的会议，第 3 天再参加最后一个，共 3 场。

代码实现

import java.util.Arrays;
import java.util.PriorityQueue;

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)$。小根堆最坏保存全部同时可参加的会议；排序栈空间取决于语言实现。

关键点总结

候选集合是「已经开始且尚未过期」的会议。

每天优先选择结束最早的会议，为未来保留更宽松的选择。

小根堆只需保存结束日；开始日通过排序指针控制入堆。

堆为空时跳到下一个开始日，避免日期范围很大时逐日扫描。

易错点总结

选择结束最晚的会议：会占用本可留给未来的宽松会议，并让紧迫会议过期。

没有删除 end < day 的会议：可能参加已经结束的会议。

把 end == day 当作过期：结束日当天仍可参加，过期条件必须是严格小于。

先选会议再加入当天开始的会议：会漏掉开始日恰好等于当天的更优候选。

堆为空仍逐日递增：日期上界大时会产生与会议数量无关的无效循环。

相似题目

题目	难度	考察点
253. 会议室 II	中等	会议要占满整个区间，堆维护的是同时进行的房间数
435. 无重叠区间	中等	按结束时间排序的经典区间不重叠贪心，无需堆
452. 用最少数量的箭引爆气球	中等	求最少打点数，等价于求区间的最大不重叠划分
621. 任务调度器	中等	约束从区间变成冷却间隔，堆按剩余次数排序
630. 课程表 III	困难	需要反悔贪心，用大根堆退掉已选的最长课程