253. Meeting Rooms II

Medium

Description

給定一個會議時間區間的陣列 intervals，求同時進行的會議最多需要多少間會議室。

Example:

Input: intervals = [[0,30],[5,10],[15,20]] Output: 2

此題為 LeetCode Premium 題目。以下解法基於題目描述撰寫。

Intuition#

找「同時進行的最大會議數」，等價於掃描線找最大重疊深度。

把每個區間拆成「開始事件 +1」和「結束事件 -1」
按時間排序後掃描，累加值的最大值就是答案
或者用 min-heap 追蹤最早結束的會議

Approaches#

1: Min-Heap (Priority Queue)#

概念: 按起點排序後，用 min-heap 追蹤正在進行的會議的結束時間。如果最早結束的會議已經結束，就釋放那間會議室。
時間複雜度: O(n log n)
空間複雜度: O(n)

class Solution {
    fun minMeetingRooms(intervals: Array<IntArray>): Int {
        intervals.sortBy { it[0] }
        val heap = java.util.PriorityQueue<Int>()
        for (interval in intervals) {
            if (heap.isNotEmpty() && heap.peek() <= interval[0]) {
                heap.poll()
            }
            heap.add(interval[1])
        }
        return heap.size
    }
}

⭐2: Sweep Line (Event Sorting)#

概念: 將所有起點和終點拆成事件，排序後掃描，追蹤同時進行的會議數
時間複雜度: O(n log n)
空間複雜度: O(n)

class Solution {
    fun minMeetingRooms(intervals: Array<IntArray>): Int {
        val starts = intervals.map { it[0] }.sorted().toIntArray()
        val ends = intervals.map { it[1] }.sorted().toIntArray()
        var rooms = 0
        var maxRooms = 0
        var s = 0; var e = 0
        while (s < starts.size) {
            if (starts[s] < ends[e]) {
                rooms++
                maxRooms = maxOf(maxRooms, rooms)
                s++
            } else {
                rooms--
                e++
            }
        }
        return maxRooms
    }
}

🔑 Takeaways#

Pattern: 掃描線 (Sweep Line) — 將區間拆成事件點，排序後掃描求最大同時值
關鍵技巧: 分開排序 start 和 end 是一個巧妙的簡化：不需要配對，只需要知道「某個會議開始了」和「某個會議結束了」