meeting rooms II [M]

This one is slightly harder than its sister problem.

the problem

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of days required to schedule all meetings without any conflicts.
This is one of those problems that seems pretty easy until you start coding it. Fortunately, there is a very intuitive solution available.

the idea

We can count the minimum number of days by achieving the minimum number of overlapping schedules. To do this, we can run all of the meetings in order of start time. If a meeting starts, increment the number of rooms used. If a meeting has ended, decrement the number of rooms used. By doing this for every single meeting, we can figure out when there are the most overlaps.

the solution

Start by marking all start and end times with a 1 and -1 respectively.

times = []
for i in intervals:
	times.append((i.start, 1))
	times.append((i.end, -11))

We also have to sort the times. End times should be sorted before start times in order to free up a room before starting a new meeting.

times.sort(key=lambda x: (x[0], x[1]))

Here, the lambda ensures we sort by time first, and tiebreak when times are equal. Our final step is to sweep through the timeline to do our counting.

used_rooms = 0
max_used_rooms = 0

for time in times:
	used_rooms += time[1]
	# keep track of max rooms at any point
	max_used_rooms = max(max_used_rooms, used_rooms)

return max_used_rooms;