給定一個會議時間區間的陣列
intervals，求同時進行的會議最多需要多少間會議室。
Example:
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2
WARNING
此題為 LeetCode Premium 題目。以下解法基於題目描述撰寫。
Intuition
TIP
找「同時進行的最大會議數」，等價於掃描線找最大重疊深度。
- 把每個區間拆成「開始事件 +1」和「結束事件 -1」
- 按時間排序後掃描，累加值的最大值就是答案
- 或者用 min-heap 追蹤最早結束的會議
Approaches
1. Min-Heap (Priority Queue) — O(n log n) / O(n)
- Idea: 按起點排序後，用 min-heap 追蹤正在進行的會議的結束時間。如果最早結束的會議已經結束，就釋放那間會議室。
- Time:
O(n log n) - Space:
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)
- Idea: 將所有起點和終點拆成事件，排序後掃描，追蹤同時進行的會議數
- Time:
O(n log n) - Space:
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) — 將區間拆成事件點，排序後掃描求最大同時值
- Key trick: 分開排序 start 和 end 是一個巧妙的簡化：不需要配對，只需要知道「某個會議開始了」和「某個會議結束了」