Meeting Rooms Problem Minimum Rooms Required in DSA Typescript

Mental Model

We want to find the smallest number of rooms needed so that no meetings overlap in the same room.

Analogy: Imagine you have several friends who want to use a single bathroom at different times. You want to know how many bathrooms you need so that no one waits.

Meetings: [1,4], [2,5], [7,9]
Timeline: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Rooms needed: ?

Dry Run Walkthrough

Input: meetings: [[1,4], [2,5], [7,9]]

Goal: Find the minimum number of rooms needed so no meetings overlap in the same room.

Step 1: Sort meetings by start time

[1,4], [2,5], [7,9]

Why: Sorting helps us check meetings in order of when they start.

Step 2: Create a min-heap for end times and add first meeting end time 4

Heap: [4]

Why: We track when rooms become free by their meeting end times.

Step 3: Check second meeting start 2 against earliest end time 4

Heap: [4,5]

Why: 2 < 4 means overlap, so we need a new room.

Step 4: Check third meeting start 7 against earliest end time 4

Remove 4 from heap, add 9 -> Heap: [5,9]

Why: 7 >= 4 means a room is free, reuse it by removing 4 and adding 9.

Result:

Heap: [5,9]
Minimum rooms needed: 2

Annotated Code

DSA Typescript

class MinHeap {
  heap: number[] = [];

  insert(val: number) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let idx = this.heap.length - 1;
    while (idx > 0) {
      let parentIdx = Math.floor((idx - 1) / 2);
      if (this.heap[parentIdx] <= this.heap[idx]) break;
      [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
      idx = parentIdx;
    }
  }

  extractMin(): number | null {
    if (this.heap.length === 0) return null;
    if (this.heap.length === 1) return this.heap.pop()!;
    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.bubbleDown();
    return min;
  }

  bubbleDown() {
    let idx = 0;
    const length = this.heap.length;
    while (true) {
      let left = 2 * idx + 1;
      let right = 2 * idx + 2;
      let smallest = idx;
      if (left < length && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < length && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === idx) break;
      [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
      idx = smallest;
    }
  }

  peek(): number | null {
    return this.heap.length > 0 ? this.heap[0] : null;
  }
}

function minMeetingRooms(intervals: number[][]): number {
  if (intervals.length === 0) return 0;

  intervals.sort((a, b) => a[0] - b[0]);

  const heap = new MinHeap();
  heap.insert(intervals[0][1]);

  for (let i = 1; i < intervals.length; i++) {
    const currentStart = intervals[i][0];
    const earliestEnd = heap.peek();

    if (earliestEnd !== null && currentStart >= earliestEnd) {
      heap.extractMin();
    }

    heap.insert(intervals[i][1]);
  }

  return heap.heap.length;
}

// Driver code
const meetings = [[1,4], [2,5], [7,9]];
console.log(minMeetingRooms(meetings));

intervals.sort((a, b) => a[0] - b[0]);

Sort meetings by start time to process in order

heap.insert(intervals[0][1]);

Add first meeting end time to heap to track room usage

const earliestEnd = heap.peek();

Check earliest room free time

if (earliestEnd !== null && currentStart >= earliestEnd) { heap.extractMin(); }

If room is free before current meeting starts, reuse it

heap.insert(intervals[i][1]);

Add current meeting end time to heap

return heap.heap.length;

Number of rooms needed equals heap size

Output

2

Complexity Analysis

Time: O(n log n) because we sort the meetings and use a heap to track room end times for n meetings

Space: O(n) because in worst case all meetings overlap and we store all end times in the heap

vs Alternative: A naive approach checks all pairs for overlap O(n^2), this heap method is more efficient for large inputs

Edge Cases

empty meetings list

returns 0 rooms needed

DSA Typescript

if (intervals.length === 0) return 0;

all meetings non-overlapping

returns 1 room needed

DSA Typescript

if (earliestEnd !== null && currentStart >= earliestEnd) { heap.extractMin(); }

all meetings fully overlapping

returns number of meetings as rooms needed

DSA Typescript

heap.insert(intervals[i][1]);

When to Use This Pattern

When you see a problem asking for minimum rooms or resources to handle overlapping intervals, use the min-heap pattern to track earliest finishing times and reuse rooms.

Common Mistakes

Mistake: Not sorting meetings by start time before processing
Fix: Sort intervals by start time first to process in chronological order

Mistake: Not removing earliest end time from heap when room is free
Fix: Check if current meeting starts after earliest end time and remove it to reuse room

Summary

Finds the minimum number of rooms needed so no meetings overlap in the same room.

Use when scheduling overlapping intervals and you want to minimize resource usage.

Sort meetings by start time and use a min-heap to track earliest finishing meeting to reuse rooms efficiently.

Practice

1. What does the "Meeting Rooms Problem Minimum Rooms Required" ask you to find given a list of meeting time intervals?

easy

A. The maximum duration of a single meeting

B. The minimum number of meeting rooms needed to hold all meetings without overlap

C. The total number of meetings scheduled

D. The earliest start time among all meetings

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum number of rooms needed so that no meetings overlap in the same room.

2. Step 2: Clarify what is NOT asked

   It is not about meeting durations, counts, or earliest times, but about room allocation to avoid conflicts.

3. Final Answer:

   The minimum number of meeting rooms needed to hold all meetings without overlap -> Option B

4. Quick Check:

   Minimum rooms = no overlapping meetings [OK]

Hint: Count overlaps to find minimum rooms needed [OK]

Common Mistakes:

• Confusing total meetings with rooms needed
• Thinking about meeting length instead of overlaps
• Ignoring overlapping intervals

2. Which TypeScript code snippet correctly sorts an array of meeting intervals by their start time?

easy

A. intervals.sort((a, b) => a[0] + b[0]);

B. intervals.sort((a, b) => b[1] - a[1]);

C. intervals.sort((a, b) => a[1] - b[0]);

D. intervals.sort((a, b) => a[0] - b[0]);

Solution

1. Step 1: Identify sorting by start time

   We want to sort intervals by their start time, which is the first element in each interval array.

2. Step 2: Check the sorting function

   The correct comparator subtracts start times: a[0] - b[0]. This sorts ascending by start time.

3. Final Answer:

   intervals.sort((a, b) => a[0] - b[0]); -> Option D

4. Quick Check:

   Sort by start time = a[0] - b[0] [OK]

Hint: Sort intervals by start time using a[0] - b[0] [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Using addition instead of subtraction in comparator
• Mixing start and end indices in comparator

3. Given the following TypeScript code, what is the output?

const intervals = [[0, 30], [5, 10], [15, 20]];

function minMeetingRooms(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  const heap: number[] = [];

  for (const interval of intervals) {
    if (heap.length && heap[0] <= interval[0]) {
      heap.shift();
    }
    heap.push(interval[1]);
    heap.sort((a, b) => a - b);
  }

  return heap.length;
}

console.log(minMeetingRooms(intervals));

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: [[0,30], [5,10], [15,20]] (already sorted)

2. Step 2: Simulate heap to track end times

   First interval: heap = [30] Second interval starts at 5, heap[0]=30 > 5, so no removal, heap = [30,10], sorted to [10,30] Third interval starts at 15, heap[0]=10 <= 15, remove 10, heap = [30], then add 20, heap = [20,30]

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Max overlapping meetings = 2 rooms needed [OK]

Hint: Track earliest end time to reuse rooms [OK]

Common Mistakes:

• Not sorting intervals before processing
• Not removing ended meetings from heap
• Assuming heap length equals total meetings

4. The following TypeScript code is intended to find the minimum number of meeting rooms needed. What is the bug?

function minMeetingRooms(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  const heap: number[] = [];

  for (const interval of intervals) {
    if (heap.length && heap[0] <= interval[0]) {
      heap.shift();
    }
    heap.push(interval[1]);
    heap.sort((a, b) => a - b);
  }

  return heap.length;
}

medium

A. Intervals are sorted by end time instead of start time

B. Heap is not sorted after push

C. The condition to remove from heap is incorrect

D. The function returns the wrong value

Solution

1. Step 1: Check sorting criteria

   The intervals are sorted by end time (a[1] - b[1]) but should be sorted by start time to process meetings in order.

2. Step 2: Understand impact of wrong sorting

   Sorting by end time breaks the logic of checking overlaps because meetings are not processed in chronological start order.

3. Final Answer:

   Intervals are sorted by end time instead of start time -> Option A

4. Quick Check:

   Sort by start time, not end time [OK]

Hint: Always sort intervals by start time first [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Not sorting heap after insertion
• Incorrect condition to remove ended meetings

5. You have the following meeting intervals: [[1,4], [2,5], [7,9], [3,6], [10,11]]. What is the minimum number of meeting rooms required to schedule all meetings without overlap?

hard

A. 4

B. 2

C. 3

D. 1

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: [[1,4], [2,5], [3,6], [7,9], [10,11]]

2. Step 2: Track overlapping meetings

   At time 1: room count = 1 At time 2: overlaps with [1,4], rooms = 2 At time 3: overlaps with [1,4] and [2,5], rooms = 3 At time 7: previous meetings ended, rooms = 1 At time 10: rooms = 1

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Max overlaps = 3 rooms needed [OK]

Hint: Count max overlaps at any time for rooms needed [OK]

Common Mistakes:

• Not sorting intervals before counting overlaps
• Underestimating overlaps by ignoring simultaneous meetings
• Assuming one room fits all meetings