253.Meeting Rooms II

Tags: [heap], [min_heap], [sort], [recursion]

Com: {fb}

Link: https://leetcode.com/problems/meeting-rooms-ii/#/description

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.

For example,
Given[[0, 30],[5, 10],[15, 20]],
return2.

More clean solution: Heap Min Heap

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x.start)
        min_heap = []

        for interval in intervals:
            if min_heap and min_heap[0] <= interval.start:
                heapq.heappop(min_heap)

            # no need push the entire interval (start, end) into the heap,
            # because we only use interval.end inside of the heap.
            heapq.heappush(min_heap, interval.end)

        return len(min_heap)

Revelation:

• Each time, we only need to check whether there exist an available room can be used for the current meeting (interval), if there exist, we pop up the previous meeting, and push the current meeting into the container. If there is no available room for current meeting, we just allocate a new room for current meeting. So we need use a container which can find which pervious meeting can finish earlier than others (the min interval.end in the current container), the min_heap is a proper container to do this task, and in the min_heap, we only need to store the interval.end, do not need store the entire interval.

Note:

• Time complexity = O(nlgn), n is the number of intervals.

Solution: Heap, Min Heap

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0

        intervals.sort(key=lambda x : x.start)
        min_heap = [] # order by interval.end

        for interval in intervals:
            if min_heap and min_heap[0][1].end <= interval.start:
                heapq.heappop(min_heap)

            heapq.heappush(min_heap, (interval.end, interval))

        return len(min_heap)

Time Limited Exceeded: Recursion

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0

        intervals.sort(key=lambda x : x.start)
        rooms = []
        return self.min_meeting_rooms_helper(intervals, 0, rooms)

    def min_meeting_rooms_helper(self, intervals, index, rooms):
        # base case
        if index >= len(intervals):
            return len(rooms)

        curr = intervals[index]

        # choice 1: put the current interval into a new room
        rooms.append([index])
        min_num_of_rooms = self.min_meeting_rooms_helper(intervals, index + 1, rooms)
        rooms.pop()

        # choice 2: try to find an existing room which can host the current interval
        for room in rooms:
            last_interval = intervals[room[-1]]
            if last_interval.end <= curr.start:
                room.append(index)
                min_num_of_rooms = min(min_num_of_rooms, self.min_meeting_rooms_helper(intervals, index + 1, rooms))
                room.pop()

        return min_num_of_rooms

Revelation:

• See the comments in the code

Time Limited Exceeded: Recursion

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def __init__(self):
        self.min_num_of_rooms = sys.maxint

    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0

        intervals.sort(key=lambda x : x.start)
        rooms = []
        self.min_meeting_rooms_helper(intervals, 0, rooms)
        return self.min_num_of_rooms

    def min_meeting_rooms_helper(self, intervals, index, rooms):
        # base case
        if index >= len(intervals):
            self.min_num_of_rooms = min(self.min_num_of_rooms, len(rooms))
            return

        curr = intervals[index]

        # choice 1: put the current interval into a new room
        rooms.append([index])
        self.min_meeting_rooms_helper(intervals, index + 1, rooms)
        rooms.pop()

        # choice 2: try to find an existing room which can host the current interval
        for room in rooms:
            last_interval = intervals[room[-1]]
            if last_interval.end <= curr.start:
                room.append(index)
                self.min_meeting_rooms_helper(intervals, index + 1, rooms)
                room.pop()

Revelation:

• The above recursion, can be converted to the recursion which is not using the global variable.