跳转至

253. 会议室 II

题目

给定一系列的会议时间间隔 intervals，包括起始和结束时间 [[s1,e1],[s2,e2],...] (si < ei)，找到所需的最小的会议室数量。

示例 1:

输入: intervals = [(0,30),(5,10),(15,20)]

输出: 2

解释: 需要两个会议室，会议室 1: (0,30)，会议室 2: (5,10),(15,20)

题解

思路 1: 数组排序

用两个数组来做，分别保存起始时间和结束时间，然后各自排个序。

然后开始遍历，如果当前起始时间小于结束时间，则结果自增 1，反之结束时间指针自增 1，这样可以找出重叠的时间段，从而安排新的会议室

  • 时间复杂度：\(O(nlogn)\)
  • 空间复杂度：\(O(n)\)
Go
func minMeetingRooms(intervals [][]int) int {
    var startTimes []int
    var endTimes []int

    for _, interval := range intervals {
        startTimes = append(startTimes, interval[0])
        endTimes = append(endTimes, interval[1])
    }

    sort.Ints(startTimes)
    sort.Ints(endTimes)

    endIdx := 0
    roomsCount := 0
    for i := 0; i < len(intervals); i++ {
        earliestEndTime := endTimes[endIdx]
        if startTimes[i] < earliestEndTime {
            roomsCount++
        } else {
            endIdx++
        }
    }

    return roomsCount
}
Python
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if len(intervals) == 0:
            return 0

        startTimes = sorted([interval[0] for interval in intervals])
        endTimes = sorted([interval[1] for interval in intervals])

        endIndex = 0
        roomsCount = 0
        for i in range(len(intervals)):
            # 新会议的开启时间 早于 上一个会议的结束时间, 此时需要一个新的会议室
            if startTimes[i] < endTimes[endIndex]:
                roomsCount += 1
            else:
                endIndex += 1

        return roomsCount

思路 2: 扫描线

TODO

参考