基于结束时间排序的会议最少房间数Golang解法是否正确？

问题描述 #

给定代表N个会议开始和结束时间的区间列表，求容纳所有会议所需的最少房间数。

示例 #

• 会议: [[1,4], [2,5], [7,9]]，输出: 2
• 会议: [[1,4], [2,3], [3,6]]，输出: 2

我的Golang解法 #

package main

import (
    "fmt"
    "sort"
)

func main() {
    intervals := NewIntervalList([][]int{{12, 13}, {13, 15}, {17, 20}, {13, 14}, {19, 21}, {18, 20}, {12, 13}})
    fmt.Println(MinMeetingRooms(intervals))
}

type Interval struct {
    Start int
    End   int
}

type Intervals []Interval

func NewIntervalList(list [][]int) Intervals {
    var intervals = make(Intervals, 0, len(list))
    for _, v := range list {
        intervals = append(intervals, Interval{Start: v[0], End: v[1]})
    }
    return intervals
}

func MinMeetingRooms(intervals Intervals) int {
    if len(intervals) < 1 {
        return 0
    }
    sort.Slice(intervals, func(a, b int) bool {
        if intervals[a].End == intervals[b].End {
            return intervals[a].Start < intervals[b].Start
        }
        return intervals[a].End < intervals[b].End
    })
    var vacantIdx int
    var roomCnt int = 1
    for i := 1; i < len(intervals); i++ {
        if intervals[i].Start < intervals[vacantIdx].End {
            roomCnt++
        } else {
            vacantIdx++
        }
    }

    return roomCnt
}

解法说明 #

• 首先根据会议结束时间对区间进行升序排序（若结束时间相同，则按开始时间升序排序）
• 用vacantIdx记录空闲房间对应的会议索引（即最早结束的会议）
• 若下一场会议与当前空闲房间的会议（最早结束的会议）冲突，则增加房间计数
• 若不冲突，则将空闲房间索引后移一位

疑问 #

我的这个解法是否正确？我在其他论坛看到，通常用堆来跟踪当前进行中所有会议的结束时间。

解答 #

你的解法不正确，存在逻辑漏洞。举个反例即可验证：
假设会议列表为[[1,5], [2,3], [4,6]]，按你的逻辑排序后得到[[2,3], [1,5], [4,6]]。
遍历过程：

1. 初始vacantIdx=0，roomCnt=1
2. 处理第二个会议[1,5]：因1 < 3，roomCnt变为2
3. 处理第三个会议[4,6]：4 > 3，所以vacantIdx变为1，此时判断4 < 5为真，roomCnt变为3

但实际所需最少房间数是2：[2,3]和[1,5]占用两个房间，[4,6]可以等[2,3]结束后复用它的房间，你的代码却错误地计算为3。

问题核心在于，你的逻辑仅跟踪了最早结束的单个会议，当后续会议可以复用更早释放的房间时，vacantIdx已经后移，无法回溯利用那些更早空闲的房间，导致错误统计房间数。

而主流的最小堆解法能避免这个问题：

1. 先按会议开始时间升序排序
2. 用最小堆存储当前所有进行中会议的结束时间，堆顶为最早结束的时间
3. 遍历每个会议：
   • 若当前会议开始时间 ≥ 堆顶结束时间，说明可复用该房间，弹出堆顶后将当前会议结束时间入堆
   • 否则，新增房间，直接将当前会议结束时间入堆
4. 最终堆的大小即为最少所需房间数

这种方式能全面跟踪所有可用空闲房间，确保每次都复用最早空闲的资源，不会遗漏复用机会。

内容的提问来源于stack exchange，提问作者Vish511