253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

Example 1

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

Example 2

Input: [[7,10],[2,4]]
Output: 1

I是看區間有無重疊，II是看需要幾間會議室，訂一個heap紀錄沒有重疊的結束時間，再看個數決定需要幾間。

Java

import java.util.*;
public class Solution {
  public static int minMeetingRooms(int[][] intervals) {
    // Store end times of each room
    Queue<Integer> minHeap = new PriorityQueue<>();
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // O(nlogn)
    /*Java 8 
    (a, b) -> Integer.compare(b[0],a[0])); //decreasing order
    (a, b) -> Integer.compare(a[0],b[0]); //increasing order
    */
    System.out.println(Arrays.deepToString(intervals));
    // [[0, 30], [5, 10], [15, 20]]
    
    for (int[] interval : intervals) {
      if (!minHeap.isEmpty() && interval[0] >= minHeap.peek()) // check head peek O(1)
        minHeap.poll(); // remove head, No overlap, we can reuse the same room O(logn)
      minHeap.offer(interval[1]); // insert offer O(logn)
    }

    return minHeap.size(); // size is required room
  }
    public static void main(String[] args) {
		int[][] slot = {{15, 20}, {0, 30}, {5, 10}};
		System.out.println(minMeetingRooms(slot));
	}  
}
>
[[0, 30], [5, 10], [15, 20]]
2

Python

T:O(nˆ2), S:O(n)

from heapq import heappush, heappop

intervals = [[0,30],[5,10],[15,20]]

class Solution(object):
    def minMeetingRooms(self, intervals):
        # intervals.sort(key=lambda it: (it[0], it[1]))
        ret, heap = 0, []

        for it in intervals:
            while heap and heap[0] <= it[0]: # if heap's root <= interval.start, continue pop heap 
                heappop(heap)
            heappush(heap, it[1]) # push interval.end
            ret = max(ret, len(heap))
        return ret
        
print(Solution().minMeetingRooms(intervals))

Follow up

Most Frequent room

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)