Skip to content

Meeting Rooms II

Meeting Rooms II

Medium Day 8 • Striver Blind 75

📌 Problem Overview

Given an array of meeting time intervals, return the minimum number of conference rooms required.

Examples & Constraints

Example 1:

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

Constraints:

0 <= intervals.length <= 10^4

💡 Approach & Intuition

Separate start and end times, sort both, use two pointers to count active overlapping meetings.

🎯 Pattern Recognition

Two Pointers / Min Heap Overlap Counter

📊 Step-by-Step Execution (Mermaid Diagram)

graph TD
    Element["Stream Element / Array Num"] --> Push["Insert into Heap (Min/Max)"]
    Push --> Up["Heapify Up to maintain order"]
    Up --> Size{"Check Heap Capacity / K Elements"}
    Size -- "Exceeds K" --> Pop["Pop Root Element"]
    Size -- "Within K" --> Peek["Peek Top Element"]
    Pop --> Peek
    Peek --> Result["Return Median / Top K"]

🐢 Brute Force Solution

Code

function minMeetingRooms(intervals) {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
  let rooms = 0, endIdx = 0;
  for (let i = 0; i < starts.length; i++) {
    if (starts[i] < ends[endIdx]) rooms++;
    else endIdx++;
  }
  return rooms;
}

Time Complexity: O(n log n)
Space Complexity: O(n)
Explanation: Two pointers on sorted starts and ends.

⚡ Optimized Solution

Code

function minMeetingRooms(intervals) {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);
  let rooms = 0, endIdx = 0;
  for (let i = 0; i < starts.length; i++) {
    if (starts[i] < ends[endIdx]) rooms++;
    else endIdx++;
  }
  return rooms;
}

Time Complexity: O(n log n)
Space Complexity: O(n)
Explanation: Chrono start/end pointer scanning.

🐾 Step-by-Step Walkthrough

Initialize State: Setup necessary pointers, dynamic programming arrays, or hash maps.
Iterate & Evaluate: Process the input according to the boundary conditions.
Update & Return: Compute the optimal answer and return early or at termination.

🎙️ FAANG Interview Pitch

If a meeting starts before the earliest ending meeting finishes, we need an extra room.

💡 Progressive Hints

Sort start times and end times independently.

⚡ Interactive Practice

👉 Solve this problem interactively in the DSA Lab