Meeting Rooms II

The problem

Each meeting in intervals is written [start, end] with start before end. A meeting uses its room from its start up to, but not including, its end. So two meetings overlap, and need different rooms, when each starts before the other ends. A meeting that starts at the exact time another ends can use the same room, and two copies of the same meeting need two rooms. Return the smallest number of rooms in which all the meetings can take place. An empty list needs 0 rooms.

What to write

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

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

Output
2

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

Output
1

Constraints

start < end.

Hints

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

1. Hint 1: Use the constraints

   A room is free again at the exact time its meeting ends, so [0, 1] and [1, 2] fit in one room. You are asked only for the number of rooms, not for which meeting goes into which room.

2. Hint 2: Ask a smaller question

   Take [0, 30], [5, 10] and [15, 20]. How many meetings are going on at time 7? At time 12? At time 17? Which of those moments decides how many rooms you need?

3. Hint 3: Name the pattern

   You need as many rooms as the largest number of meetings in progress at one moment. That number changes only when a meeting starts or ends. So list those moments, sort them, and walk through them once while counting. Sorting the starts and ends of intervals and passing over them in time order is a sorted interval sweep. Read the lesson on sorted interval sweep.

4. Hint 4: State the invariant

   Once all the events up to some time are applied, the count is the number of meetings that have started and not yet ended. At equal times the ends are applied first, so a meeting that ends at 10 is never counted together with one that starts at 10.

5. Hint 5: Sketch the pseudocode

   Make a list of events: (start, +1) and (end, -1) for every meeting. Sort it by time, and at equal times put -1 before +1. active = 0, best = 0. For each event: add its +1 or -1 to active, then set best to the larger of best and active. Return best.

Solution

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

Approach

Sweep sorted start and end events, processing ends before starts at equal times. Peak simultaneous occupancy is the room count.

The slow way

The number of meetings in progress can only go up at a start time. So for each meeting's start, go through all the meetings, count the ones in progress at that moment, and keep the largest count. It is correct, but that is n passes over n meetings: about n × n steps.

The insight

You do not need to know which meeting is in which room. The number of meetings in progress goes up by one at every start and down by one at every end, and nothing else changes it. Put all those moments in time order and follow the count: its highest value is the answer.

Step by step

1. Turn each meeting into two events: a start (+1) and an end (-1). The number of meetings in progress changes only when one starts or ends. An event records one such moment: its time, and +1 for a start or -1 for an end.
2. Sort the events by time, with ends before starts at equal times. The count has to follow the clock. At equal times an end goes first, because a room is free again at its meeting's end time, and a meeting that starts then can take it.
3. Start with no meeting in progress and a highest count of zero. Before the first event nothing is going on, so both numbers begin at zero. With an empty list there are no events and the answer stays zero.
4. Apply each event in order to the count of meetings in progress. A start adds one meeting in progress and an end takes one away. Once all the events up to some time are applied, the count is the number of meetings that have started and not yet ended.
5. Remember the highest count seen so far. Meetings that are in progress together all need different rooms. So the highest count is a number of rooms you cannot do without.
6. The highest count is the number of rooms needed. That many rooms are also enough. Whenever a meeting starts, the count including it is at most the highest count, so at least one of the rooms is free for it.

The same numbered steps are the comments in each solution.

function solve(intervals) {
  // 1. Turn each meeting into two events: a start (+1) and an end (-1)
  const events = [];
  for (const [start, end] of intervals) {
    events.push([start, 1], [end, -1]);
  }
  // 2. Sort the events by time, with ends before starts at equal times
  // a[0] - b[0] orders by time. When it is 0, a[1] - b[1] puts -1 before 1.
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  // 3. Start with no meeting in progress and a highest count of zero
  let active = 0,
    best = 0;
  // 4. Apply each event in order to the count of meetings in progress
  for (const [, delta] of events) {
    active += delta;
    // 5. Remember the highest count seen so far
    best = Math.max(best, active);
  }
  // 6. The highest count is the number of rooms needed
  return best;
}

function solve(intervals: number[][]): number {
  // 1. Turn each meeting into two events: a start (+1) and an end (-1)
  const events: number[][] = [];
  for (const [start, end] of intervals) {
    events.push([start, 1], [end, -1]);
  }
  // 2. Sort the events by time, with ends before starts at equal times
  // a[0] - b[0] orders by time. When it is 0, a[1] - b[1] puts -1 before 1.
  events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  // 3. Start with no meeting in progress and a highest count of zero
  let active = 0,
    best = 0;
  // 4. Apply each event in order to the count of meetings in progress
  for (const [, delta] of events) {
    active += delta;
    // 5. Remember the highest count seen so far
    best = Math.max(best, active);
  }
  // 6. The highest count is the number of rooms needed
  return best;
}

def solve(intervals):
    # 1. Turn each meeting into two events: a start (+1) and an end (-1)
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
    # 2. Sort the events by time, with ends before starts at equal times
    # Pairs are compared by time first, then by the second number: -1 before 1.
    events.sort()
    # 3. Start with no meeting in progress and a highest count of zero
    active = best = 0
    # 4. Apply each event in order to the count of meetings in progress
    for _, delta in events:
        active += delta
        # 5. Remember the highest count seen so far
        best = max(best, active)
    # 6. The highest count is the number of rooms needed
    return best

Example 1, traced

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

Output
2

Why it works

Once all the events at one time are applied, the count is the number of meetings in progress then, and because ends go first it is never higher partway through them. Meetings in progress together need separate rooms, so the answer is at least the highest count. That many are enough: when a meeting starts, the count including it is at most the highest count, so a room is free.

Time and space

Time O(n log n), extra space O(n). n meetings give 2n events. Sorting them takes about n log n steps, and the pass after it does one addition and one comparison per event, so the time is O(n log n). The event list holds 2n pairs: O(n) space.

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

• At equal times, apply the end before the start. Sorted by time alone, the list [1, 2], [0, 1] keeps the start at 1 ahead of the end at 1, and the count reaches 2: 2 rooms instead of 1.
• The answer is not one plus the most meetings that any single meeting overlaps. In example 1, [0, 30] overlaps two others, which would give 3, but those two are never in progress at the same time.
• Return the highest count, not the count at the end. After the last event every meeting is over, so the final count is always 0.

Pattern

Sorted interval sweep. Builds on Meeting Rooms.

Keep going