Free Intervals lessonsIntervals · Stage 1 · Sweep line · Step 1

How many rooms?

Find the fewest rooms that hold all meetings at once by sorting starts and ends separately and sweeping through time. About 18 minutes.

Starts and ends, apart

A meeting is [start, end), so one ending at 10 and another starting at 10 can share a room. You need the fewest rooms for all meetings.

Which meeting is in which room does not matter. All that matters is how many are running at one time. So pull the starts and the ends apart into two sorted lists. Time moves forward: a start takes a room, an end gives one back.

Rooms needed: equals the most meetings running at once.

Sort starts and ends: as two separate lists.

Reuse or open

Go through the starts in order, with a pointer j at the earliest end not yet used. If the next start is at or after that end, some meeting has finished, so its room is free: reuse it and move j along.

Otherwise every meeting so far is still running, so open a new room. The number of rooms opened is the answer, and each list is walked once after sorting.

Start at or after the earliest end? reuse a room.

Otherwise: open a new room.

In code

starts.sort()
ends.sort()

Meetings [1, 10], [2, 6], [4, 8], [9, 12]. Sorted starts 1, 2, 4, 9. Sorted ends 6, 8, 10, 12.

Start 1: no meeting has ended yet. Open room 1.

Move 1 of 4

Quick check

Meetings [1, 3] and [3, 5]. How many rooms?

Show the answer

1. The first ends at 3 as the second starts at 3, so the room is free.

Your problem

Meeting rooms needed

You are given meetings, each as [start, end), meaning it occupies the room from start up to but not including end. Return the fewest rooms needed to hold all the meetings.

Example

meetings = [[0, 30], [5, 10], [15, 20]] → 2

0 ≤ meetings.length ≤ 100,000 · 0 ≤ start < end ≤ 1,000,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.