253. 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]],
return 2.
Solution: Sweep Line
class Solution(object):
def minMeetingRooms(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
timestamps = []
for interval in intervals:
timestamps.append([interval.start, True])
timestamps.append([interval.end, False])
timestamps.sort()
max_rooms = 0
rooms = 0
for _, start in timestamps:
if start:
rooms += 1
max_rooms = max(max_rooms, rooms)
else:
rooms -= 1
return max_rooms