LeetCode 253. 会议室 II

Categories:

题目描述
思路分析
1. 解法一：最小堆（推荐）
2. 解法二：差分数组 / 事件扫描线
相似题目

题目描述

✅ 253. 会议室 II

思路分析

解法一：最小堆（推荐）

核心思路：

最少会议室数等于同一时刻最大并发会议数。

按开始时间对所有会议排序，模拟按时间顺序依次安排会议室。

维护一个最小堆，存储所有正在进行中的会议的结束时间，堆顶是最早结束的会议室。

对每个新会议 [start, end]：若堆顶结束时间 ≤ start，说明该会议室已空闲，弹出堆顶复用；否则新开一间会议室，直接将 end 压入堆。

遍历结束后，堆的大小即为所需最少会议室数。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示会议数量，排序 O(n log n)，每次堆操作 O(log n)，共 n 次

空间复杂度：O(n)，堆中最多存放 n 个结束时间

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        // 按会议开始时间升序排序
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        // 最小堆：存放所有正在使用的会议室的结束时间，堆顶为最早结束的会议室
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int[] interval : intervals) {
            // 堆顶会议室已结束，可以复用
            if (!minHeap.isEmpty() && minHeap.peek() <= interval[0]) {
                minHeap.poll();
            }
            // 将当前会议的结束时间加入堆（复用或新开会议室）
            minHeap.offer(interval[1]);
        }
        return minHeap.size();
    }
}

import (
    "container/heap"
    "sort"
)

// MinHeap 实现最小堆，存储会议结束时间
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(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func minMeetingRooms(intervals [][]int) int {
    // 按会议开始时间升序排序
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    h := &MinHeap{}
    heap.Init(h)
    for _, interval := range intervals {
        // 堆顶会议室已结束，可以复用
        if h.Len() > 0 && (*h)[0] <= interval[0] {
            heap.Pop(h)
        }
        // 将当前会议的结束时间加入堆（复用或新开会议室）
        heap.Push(h, interval[1])
    }
    return h.Len()
}

解法二：差分数组 / 事件扫描线

核心思路：

将每个会议拆成两个事件：开始时间 +1（有会议占用会议室），结束时间 -1（有会议室释放）。

将所有事件按时间升序排序，同一时刻先处理结束事件再处理开始事件（避免结束和开始同时刻被重复计数）。

扫描所有事件，累加计数，过程中的最大值即为最大并发会议数，也就是所需最少会议室数。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示会议数量，构造并排序 2n 个事件需要 O(n log n)

空间复杂度：O(n)，存储 2n 个事件

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        // 分别提取开始时间和结束时间并排序
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int rooms = 0;
        int maxRooms = 0;
        // 双指针扫描：s 指向开始时间，e 指向结束时间
        int e = 0;
        for (int s = 0; s < n; s++) {
            // 当前会议开始前，若有会议已结束则释放一间会议室
            if (starts[s] >= ends[e]) {
                rooms--;
                e++;
            }
            // 为当前会议分配一间会议室
            rooms++;
            maxRooms = Math.max(maxRooms, rooms);
        }
        return maxRooms;
    }
}

import "sort"

func minMeetingRooms(intervals [][]int) int {
    n := len(intervals)
    // 分别提取开始时间和结束时间并排序
    starts := make([]int, n)
    ends := make([]int, n)
    for i, interval := range intervals {
        starts[i] = interval[0]
        ends[i] = interval[1]
    }
    sort.Ints(starts)
    sort.Ints(ends)
    rooms, maxRooms, e := 0, 0, 0
    // 双指针扫描：s 指向开始时间，e 指向结束时间
    for s := 0; s < n; s++ {
        // 当前会议开始前，若有会议已结束则释放一间会议室
        if starts[s] >= ends[e] {
            rooms--
            e++
        }
        // 为当前会议分配一间会议室
        rooms++
        if rooms > maxRooms {
            maxRooms = rooms
        }
    }
    return maxRooms
}

相似题目

题目	难度	考察点
252. 会议室	简单	排序
56. 合并区间	中等	贪心、排序
435. 无重叠区间	中等	贪心
452. 用最少数量的箭引爆气球	中等	贪心、排序
1353. 最多可以参加的会议数目	中等	贪心、堆
57. 插入区间	中等	区间合并
759. 员工空闲时间	困难	堆、排序
1851. 包含每个查询的最小区间	困难	排序、堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/86099077