meeting rooms [E]

I didn’t have time to do a question yesterday, so I will do two today.

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), determine if a person could add all meetings to their schedule without any conflicts.

the idea

If two meetings are conflicting, the start time of one meeting will be earlier than the end time of another. Therefore, if we sort all of the meetings by start time, we can compare all consecutive pairs of meetings (0 and 1, 1 and 2, etc.) to see if their times are compatible. Since the meetings with the closest start times will always create the largest conflict, we do not need to consider non-consecutive pairs.

the solution

Start by sorting the intervals by start time.

intervals.sort(key=lambda x: x.start)

We can now loop through the intervals starting from the second interval. Compare each interval to the one before it, checking for conflicts.

for i in range(1, len(intervals)):
	if intervals[i].start < intervals[i-1].end:
		return False
return True