What is the brute force approach and complexity for Meeting Rooms II?

For each meeting's start, count how many meetings are running at that moment with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Meeting Rooms II?

Two sorted lists of times; running = started − ended at each start with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Meeting Rooms II?

Look for key signals in the prompt: "minimum number of rooms" indicates = the maximum number of meetings running at the same moment.; "list of [start, end]" indicates Intervals → think in events on a timeline: +1 at a start, −1 at an end.; "a meeting is over at its end time" indicates Tie rule: at the same time, process the end before the start (`ends[j] ≤ starts[i]`)..

Meeting Rooms II

Medium·LeetCode #253 Premium Pro OnlyMedium

LeetCode

Problem Statement

You get a list of meetings. Meeting i runs from intervals[i][0] to intervals[i][1].

Every meeting needs its own room while it is running. Return the smallest number of rooms that can hold all the meetings.

A meeting is over at its end time, so a room freed at 10 can be used by a meeting starting at 10.

Input

A list intervals of [start, end] pairs.

Output

One integer: the minimum number of rooms needed.

Example 1

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

Output: 2

[0,30] needs a room the whole time. [5,10] and [15,20] don't overlap each other, so they can share a second room.

Example 2

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

Output: 1

The meetings never overlap, so one room is enough.

Example 3

Input: intervals = [[1,4],[4,9],[2,6],[5,8]]

Output: 3

At time 5, meetings [4,9], [2,6] and [5,8] are all running. [1,4] ended at 4, so its room went to [4,9].

Constraints

• 1 ≤ intervals.length ≤ 10^4
• 0 ≤ start < end ≤ 10^6

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimum number of rooms”

→ = the maximum number of meetings running at the same moment.

“list of [start, end]”

→ Intervals → think in events on a timeline: +1 at a start, −1 at an end.

“a meeting is over at its end time”

→ Tie rule: at the same time, process the end before the start (`ends[j] ≤ starts[i]`).

Approach Complexity Ladder

Brute Force — count at every start timeO(N²)O(1)

For each meeting's start, count how many meetings are running at that moment

Better — sort by start + min-heap of end timesO(N log N)O(N)

Assign rooms in start order; a min-heap tells you the room that frees up first

Optimal — sort starts and ends separately, sweepO(N log N)O(N)

Two sorted lists of times; running = started − ended at each start

Brute Force Intuition

The rooms needed equals the most meetings running at once. The count only rises when a meeting starts, so the busiest moment is some start time. For each meeting i, count the meetings j with start_j ≤ start_i < end_j. Return the biggest count.

Recognition rule for this sub-pattern:

How many things are active at the same time? Sweep events in time order, or keep a min-heap of end times.

Remember this · Intervals

Trigger

Input is [start, end] pairs; overlap, merge, insert, meeting rooms, free time, minimum removals.

Think

After sorting, do I only ever need to compare against the most recent interval?

Key question

Sort by start or by end — which one makes the greedy choice obvious?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Intervals translate into production architectures and low-level memory mechanics.

LLD Architecture