Meeting Rooms

The problem

Each meeting in intervals is written [start, end] with start before end. A meeting lasts from its start up to, but not including, its end. So two meetings overlap when each starts before the other ends, and a meeting that starts at the exact time another ends does not overlap it. Two copies of the same meeting do overlap. Return true if no two meetings overlap, which means one person can attend them all, and false otherwise. The meetings come in no particular order, and an empty list gives true.

What to write

function solve(intervals: number[][]): boolean

Input
intervals = [[0,30],[5,10],[15,20]]

Output
false

Input
intervals = [[7,10],[2,4]]

Output
true

Constraints

Intervals are [start,end) with start < end; a meeting may start exactly when another ends.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   One person can attend everything exactly when no two meetings overlap. A meeting may start at the exact time another ends, so [0, 1] and [1, 2] are fine together. The meetings come in no particular order.

2. Hint 2: Ask a smaller question

   Think of your own calendar for one day. To see whether any two appointments clash, you do not check each one against all the others. In what order do you read them, and which appointment do you compare each one with?

3. Hint 3: Name the pattern

   Sort the meetings by start time. If any two meetings overlap, then two neighbors in the sorted list overlap, so one pass that compares each meeting with the one before it is enough. Sorting intervals and handling them one by one in that order is a sorted interval sweep. The signal: a question about overlaps among intervals that come unsorted. Read the lesson on sorted interval sweep.

4. Hint 4: State the invariant

   As long as no clash has been found, every meeting visited so far starts at or after the end of the one before it. So the ends only grow along the list, and the meeting right before the current one is the last of them to end.

5. Hint 5: Sketch the pseudocode

   Sort the meetings by start. For each meeting from the second one on: if its start is less than the end of the meeting before it, return false. If the loop finishes, return true.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Sort meetings by start time and check neighboring intervals for overlap.

The slow way

Compare every meeting with every other one, and return false as soon as two of them overlap. It is correct, but n meetings make about n × n / 2 pairs, and most of those pairs lie far apart in time and could never clash.

The insight

Sort the meetings by start time. If a meeting overlaps any later one, it also overlaps the very next one, because the next one starts no later than all the others after it. So comparing each meeting with its neighbor is enough.

Step by step

1. Put the meetings in order of their start time. In order of start, if any two meetings clash, some two neighbors clash as well. So meetings that are far apart in the list never need to be compared.
2. Compare each meeting with the one right before it. The comparing starts at the second meeting, because the first has nothing before it. With one meeting or none, the loop does not run at all.
3. It starts before the previous one ends: they clash, return false. Both meetings would need the person at the same moment, so the answer is already known. "Before" is strict: the end time is not part of a meeting, so the next one may start exactly then.
4. No neighbors clash, so no meetings clash at all: return true. Every meeting starts at or after the end of the one before it, so the meetings follow one another without sharing a moment. An empty list and a single meeting also end up here.

The same numbered steps are the comments in each solution.

function solve(intervals) {
  // 1. Put the meetings in order of their start time
  intervals.sort((a, b) => a[0] - b[0]);
  // 2. Compare each meeting with the one right before it
  for (let i = 1; i < intervals.length; i++) {
    // 3. It starts before the previous one ends: they clash, return false
    if (intervals[i][0] < intervals[i - 1][1]) return false;
  }
  // 4. No neighbors clash, so no meetings clash at all: return true
  return true;
}

function solve(intervals: number[][]): boolean {
  // 1. Put the meetings in order of their start time
  intervals.sort((a, b) => a[0] - b[0]);
  // 2. Compare each meeting with the one right before it
  for (let i = 1; i < intervals.length; i++) {
    // 3. It starts before the previous one ends: they clash, return false
    if (intervals[i][0] < intervals[i - 1][1]) return false;
  }
  // 4. No neighbors clash, so no meetings clash at all: return true
  return true;
}

def solve(intervals):
    # 1. Put the meetings in order of their start time
    meetings = sorted(intervals, key=lambda meeting: meeting[0])
    # 2. Compare each meeting with the one right before it
    # zip pairs each meeting with the next: (first, second), (second, third), ...
    for previous, current in zip(meetings, meetings[1:]):
        # 3. It starts before the previous one ends: they clash, return false
        if current[0] < previous[1]:
            return False
    # 4. No neighbors clash, so no meetings clash at all: return true
    return True

Example 2, traced

Input
intervals = [[7,10],[2,4]]

Output
true

Why it works

Suppose two meetings overlap, and call the one that comes first in sorted order A. The meeting right after A starts no later than any other meeting after A, so that neighbor also starts before A ends. The loop finds this pair. And if no neighbors overlap, each meeting is over when the next one starts, so no two overlap.

Time and space

Time O(n log n), extra space O(n). Sorting n meetings takes about n log n steps, and the pass makes at most n - 1 comparisons: O(n log n) time. Python makes a sorted copy and a second copy for the pairing, and JavaScript's sort can use working space that grows with n: O(n) space either way.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Sort before you compare neighbors. In the given order, example 2 has [7, 10] right before [2, 4]. The start 2 comes before the end 10, so the loop returns false. The right answer is true.
• A meeting may start at the exact time the previous one ends. Testing "at or before" instead of "before" makes [0, 1] and [1, 2] a clash and returns false instead of true.
• In JavaScript, give sort a comparison function. The plain sort() compares the meetings as text, so [10, 12] comes before [2, 4], and these two meetings, which do not overlap, return false.

Pattern

Sorted interval sweep. Builds on Merge Intervals.

Keep going