253. Meeting Rooms II

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

Python Solution 1: time complexity O(n log(n)) (Beat 53.89%)
Sort all time points and label the start and end points. Move a vertical line from left to right.
When it meets a start point, curr_rooms += 1. When it meets an end point, curr_rooms -= 1.
(if there is a tie: put end point before start point). Update the maximal occupied rooms during the move.

    def minMeetingRooms(self, intervals):
        lst = []
        for start, end in intervals:
            lst.append((start, 1))
            lst.append((end, -1))
        lst.sort()
        res, curr_rooms = 0, 0
        for t, n in lst:
            curr_rooms += n
            res = max(res, curr_rooms)
        return res

Python Solution 2: time complexity O(n * log(max(l_heap))) (Beat 95.82%, max(l_heap) <= n)

    def minMeetingRooms(self, intervals):
        intervals.sort(key = lambda x: x[0])
        res = 0
        heap, heap_size = [], 0
        for interval in intervals:
            while heap and heap[0] <= interval[0]:
                heapq.heappop(heap)
                heap_size -= 1
            heapq.heappush(heap, interval[1])
            heap_size += 1
            res = max(res, heap_size)
        return res