We define a dict, with the key being the room number and value being the end time after which the room will be available.
Then it's all about updating the dictionary. If the upcoming event can be shoehorn into one of the existing rooms, it means the start time will not be earlier than the end time of that room. If no room satisfies that, we open a new one.
Note that we have to sort the start time first as we don't want a late event block all other early events. First event, first schedule.
Then answer is to return the size of the dict.
# Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution(object): def checkdict(self,mydict,starttime): for key,value in mydict.iteritems(): if value <= starttime: return key return '-1' def minMeetingRooms(self, intervals): """ :type intervals: List[Interval] :rtype: int """ intervals.sort(key = lambda x:x.start) res = collections.defaultdict(int) for i in xrange(len(intervals)): retval = self.checkdict(res,intervals[i].start) if retval =='-1': newkey = str(len(res)+1) res[newkey]=intervals[i].end else: res[retval] = intervals[i].end return len(res)