Last active 5 days ago

Interview prep notes

meetingrooms.md Raw

Interval Problems: Meeting Rooms I and II

Interval questions come up constantly because they test sorting, greedy reasoning and heaps all at once.

Meeting Rooms I (can one person attend all meetings?)

Sort by start time and check whether any meeting starts before the previous one ends.

def can_attend(intervals):
    intervals.sort()
    return all(intervals[i][0] >= intervals[i-1][1]
               for i in range(1, len(intervals)))

Meeting Rooms II (minimum number of rooms)

Sort by start; keep a min-heap of end times for rooms in use. If the earliest-ending room is free when the next meeting starts, reuse it.

import heapq
def min_rooms(intervals):
    intervals.sort()
    ends = []
    for s, e in intervals:
        if ends and ends[0] <= s:
            heapq.heapreplace(ends, e)
        else:
            heapq.heappush(ends, e)
    return len(ends)

O(n log n) time. An equally good alternative is a sweep line: sort all starts and all ends separately, walk both with two pointers, and track the maximum number of meetings open at once.

Clarify the boundary

Does a meeting ending at 10:00 conflict with one starting at 10:00? Usually no, hence <= above, but ask the interviewer. It's an easy way to show care.

Related problems

  • Merge Intervals (56): sort, then extend or append.
  • Non-overlapping Intervals (435): greedy by end time, counting removals.
  • Insert Interval (57) and Employee Free Time (759).

Disclosure: I'm on the team behind Linkjob AI, a coding interview assistant.