Meeting rooms: sort by start time and check adjacent conflicts

Coding Challenges
, ,
1

Problem. Given meeting intervals, return True if one person can attend them all and False otherwise.

This is the classic overlap detection after sorting pattern.

Examples:

  • intervals = [[0,30],[5,10],[15,20]] → False
  • intervals = [[7,10],[2,4]] → True
  • intervals = [[1,5],[5,8]] → True

Solution. Sort by start time and compare each interval with the previous one. Any start time that is earlier than the previous end creates a conflict.

def can_attend_meetings(intervals):
    intervals.sort(key=lambda interval: interval[0])
    for index in range(1, len(intervals)):
        if intervals[index][0] < intervals[index - 1][1]:
            return False
    return True

O(n log n) time, O(1) extra space if sorting in place.

Gotchas.

  • Meetings that touch at endpoints are usually allowed because one ends exactly when the next starts.
  • You only need to compare neighbors after sorting by start time.
  • This is a boolean feasibility question, not the room-count variant.

Run: Meeting Rooms