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.

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

解析

whenever there is a start meeting, we need to add one room. But before adding rooms, we check to see if any previous meeting ends, which is why we check start with the first end. When the start is bigger than end, it means at this time one of the previous meeting ends, and it can take and reuse that room. Then the next meeting need to compare with the second end because the first end's room is already taken. One thing is also good to know: meetings start is always smaller than end. Whenever we pass a end, one room is released.

for example, we have meetings that span along time as follows:

|_____|
      |______|
|________|
        |_______|

Then, the start time array and end time array after sorting appear like follows:

||    ||
     |   |   |  |

+----------------------> new room #1 for meeting "a"
|+---------------------> no meeting finish, new room #2 for meeting "b"
||    +----------------> one meeting finished at time "w", maybe #1, maybe #2, not important!
||    |                           meeting "c" use this old room.
||    |+---------------> no more meeting finish, new room #2 for meeting "b"
ab    cd
||    ||                <- start time (4 meetings begun at time a,b,c,d)
     |   |   |  |       <- end time (they finished at w,x,y,z, order not important)
     w   x   y  z

# 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
        """
        starts = []
        ends = []
        for meeting in intervals:
            starts.append(meeting.start)
            ends.append(meeting.end)
        starts.sort()
        ends.sort()
        e = 0
        numRoom = 0 
        for s in xrange(len(starts)):
            if starts[s] < ends[e]:
                numRoom += 1
            else:
                e += 1
        return numRoom