vvrf / DSA.log

问题拆解

给一批会议的起止时间，问最少需要多少间会议室才能让所有会议不冲突地开完。答案其实是一个瞬时量：某一时刻同时进行的会议有几场，那一刻就需要几间房；全天的最大并发数就是最终答案。

朴素做法是模拟分配：会议按开始时间排序，每来一场就在已有房间里找一间“上一场已结束”的，找不到就新开。直接实现要对每场会议扫一遍所有房间，O(n²)；用最小堆维护各房间的最早结束时间可以降到 O(n log n)，堆的大小峰值就是答案。

但有一个更轻的观察：我们只关心“需要几间房”，不关心“哪场会议进哪间房”。把所有开始时间和所有结束时间拆成两个独立的序列分别排序——排序打乱了起止时间的配对关系，可这不影响并发数的统计：每个开始事件让并发数加一，每个结束事件让它减一，事件发生的顺序只由时间决定。

下一场会议的开始时间早于当前最早的结束时间，说明没有任何房间来得及腾出来，只能加一间；否则就复用刚结束的那间。房间数只增不减，因为我们要的是峰值。

起止时间分离排序 + 双指针

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, e = 0;
    for (int s = 0; s < n; s++) {
        if (starts[s] < ends[e]) {
            rooms++; // 开始时没有房间腾出，新开一间
        } else {
            e++; // 复用最早结束的房间
        }
    }
    return rooms;
}

def minMeetingRooms(intervals: list[list[int]]) -> int:
    starts = sorted(s for s, _ in intervals)
    ends = sorted(e for _, e in intervals)
    rooms = e = 0
    for s in starts:
        if s < ends[e]:
            rooms += 1  # 开始时没有房间腾出，新开一间
        else:
            e += 1  # 复用最早结束的房间
    return rooms

func minMeetingRooms(intervals [][]int) int {
    n := len(intervals)
    starts := make([]int, n)
    ends := make([]int, n)
    for i, iv := range intervals {
        starts[i] = iv[0]
        ends[i] = iv[1]
    }
    slices.Sort(starts)
    slices.Sort(ends)
    rooms, e := 0, 0
    for _, s := range starts {
        if s < ends[e] {
            rooms++ // 开始时没有房间腾出，新开一间
        } else {
            e++ // 复用最早结束的房间
        }
    }
    return rooms
}

pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
    let mut starts: Vec<i32> = intervals.iter().map(|iv| iv[0]).collect();
    let mut ends: Vec<i32> = intervals.iter().map(|iv| iv[1]).collect();
    starts.sort_unstable();
    ends.sort_unstable();
    let mut rooms = 0;
    let mut e = 0;
    for &s in &starts {
        if s < ends[e] {
            rooms += 1; // 开始时没有房间腾出，新开一间
        } else {
            e += 1; // 复用最早结束的房间
        }
    }
    rooms as i32
}

指针 s 走开始序列，e 停在“最早的尚未被复用的结束时间”上。每场会议开始时二选一：starts[s] < ends[e] 就加房间，否则把 e 前移表示复用。最容易错的是边界比较：starts[s] == ends[e] 时必须走复用分支——一场会议 10 点结束、另一场 10 点开始，同一间房交接即可。把 < 写成 <= 会多算一间。另外 e 不会越界：复用一次消耗一个结束事件，而结束事件和开始事件一样多。

顺带一提最小堆做法：会议按开始时间排序，堆里存各房间的结束时间，堆顶结束得早于当前会议开始就弹出复用，历史堆大小的峰值即答案——思路等价，代码略长，但能顺便回答“每场会议分在哪间房”。

复杂度

指标	复杂度	原因
时间	`O(n log n)`	两次排序占主导，双指针扫描是线性的
空间	`O(n)`	拆出的两个时间数组

可以迁移的模式

求“最少资源数”时先翻译成“最大并发数”，答案是峰值而不是过程；
当问题只关心数量、不关心配对关系时，大胆拆散区间的起止端点分别排序；
起点与终点相等时算不算重叠，是所有区间题都要先跟题意对齐的边界。

这套“事件化 + 排序扫描”的手法同样适用于机场停机位、地铁最大在车人数等一切求峰值并发的问题。