253.md

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

• Time O(nlgn)
• Space O(n)

import heapq


class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        intervals = sorted(intervals, key=lambda x: x[0])
        heap = []
        rooms = 0
        for interval in intervals:
            if len(heap) and (interval[0] >= (heap[0])):
                heapq.heappop(heap)
            heapq.heappush(heap, interval[1])
            rooms = max(rooms, len(heap))
        return rooms