Faangprep Logo
Log inStart free
Browse curriculum

Meeting Rooms II

Meeting Rooms II asks for the minimum number of conference rooms needed to schedule all meetings, solved with the sweep line algorithm.

A room is only ever gained or given up at a moment when a meeting starts or ends, so those are the only moments worth visiting. Read them in time order, add a room on every start and release one on every end, and the largest the count ever reaches is the answer. Switch the tie-break to see the one ordering decision the whole thing turns on.

READY

Schedule

A

B

C

D

0

30

Moments · in time order

+0

A

+5

B

-10

B

+10

D

-15

D

+15

C

-20

C

-30

A

Rooms

0

Peak

0

Needed

2

 

4 meetings, and the question is how many rooms the day needs. Comparing every pair to see which overlap would answer it, and would take 6 comparisons to do it — but no room is ever needed at a moment when nothing starts or ends, so only those 8 moments have to be looked at.

Next

The 8 moments in time order, each one either a meeting starting or a meeting ending. Where a start and an end share a time the end is read first, because the room is free the instant the meeting is over.

Schedule

Tie-break

Intuition

The Core Idea: Instead of checking every minute of the day to see how many meetings are happening, we only care about the moments when the number of active meetings changes.

These moments are the Start and End times of the meetings.

Imagine a vertical line sweeping across the timeline. Every time it hits a Start, we need a room (+1). Every time it hits an End, a room becomes free (-1).

Concept

Sweep Line (Chronological Ordering):

  • Events: Deconstruct every interval [start, end] into two separate events: (start, +1) and (end, -1).
  • Sorting: Sort all events by time. If times are equal, process the End event first (to free up the room before re-allocating it).
  • Scanning: Iterate through the sorted events, maintaining a running sum of active meetings. The maximum value of this sum is the answer.

How it Works

The visualizer effectively sorts the start and end times.

  1. Timeline: Meetings are placed on a timeline.
  2. Scan: A vertical line moves from left to right.
  3. Counter: As the line passes a 'Start', the 'Active Rooms' counter increases. As it passes an 'End', it decreases.
  4. Result: The peak value of the counter is recorded as the minimum rooms required.

Step-by-Step Breakdown

1. Separate: Create an array of start times and an array of end times.
2. Sort: Sort both arrays.
3. Two Pointers: Use s_ptr for starts and e_ptr for ends.
4. Iterate:
    - If start[s_ptr] < end[e_ptr]: A meeting starts. rooms++. s_ptr++.
    - Else: A meeting ends. rooms-- (or reuse). e_ptr++.
5. Track Max: Keep track of the maximum rooms needed at any point.

When to Use

  • Finding maximum concurrency/overlap in intervals.
  • Resource allocation problems (rooms, platforms, bandwidth).
  • "Merge Intervals" variations.

When NOT to Use

  • When you need to select a subset of non-overlapping intervals (Activity Selection / Greedy).
  • When intervals have weights/values and you want to maximize value (Weighted Interval Scheduling / DP).

How to Identify

"Minimum resources required", "Maximum simultaneous events", "Find the point of maximum overlap".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Introduction

Next

Introduction

Frequently Asked Questions

What is Meeting Rooms II?

Given meeting intervals, find the minimum number of rooms required to host all meetings without overlap.

Sweep Line vs Priority Queue?

Both work! Sweep line sorts all points; Priority Queue tracks the earliest ending room for each new start.

Why does Arrival/Departure sorting work?

Because if a meeting starts at the same time another ends, sorting "End before Start" ensures you can reuse the same room.