253. Meeting Rooms II

Meeting Rooms II - LeetCode

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

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

Example 2: Input: intervals = [[7,10],[2,4]] Output: 1

Constraints:

1 <= intervals.length <= 104 0 <= starti < endi <= 106


  • code
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        rooms = [intervals[0][1]] # end time
        for i in range(1, len(intervals)):
            cur_start, cur_end = intervals[i]
            for r_index in range(len(rooms)):
                if cur_start >= rooms[r_index]:
                    rooms[r_index] = cur_end
                    break
            else:
                rooms.append(cur_end)
                
        return len(rooms)        
  • code
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        rooms = [intervals[0][1]] # end time
        for i in range(1, len(intervals)):
            cur_start, cur_end = intervals[i]
            if cur_start >= rooms[0]: # only need to compare to the existed minimum end time
                heapq.heappop(rooms)
            heapq.heappush(rooms, cur_end)
                
        return len(rooms)    
  • code
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> rooms = new PriorityQueue<>();
        for (int[] interval: intervals){
            rooms.offer(interval[1]);
            if (interval[0] >= rooms.peek()){
                rooms.poll();
            }
        }
        return rooms.size();
    }
}