Meeting Rooms Problem Minimum Rooms Required in DSA Typescript - Execution Trace

Concept Flow - Meeting Rooms Problem Minimum Rooms Required

Sort intervals by start time

↓

Initialize min-heap for end times

↓

For each interval

↓

Check if earliest end time <= current start

↓

Pop from heap

↓

Push current end time to heap

↓

Repeat for all intervals

↓

Heap size = minimum rooms needed

Sort intervals by start time, use a min-heap to track end times of ongoing meetings, reuse rooms if possible, and the heap size at the end is the minimum rooms required.

Execution Sample

DSA Typescript

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;
}

This code sorts meetings by start time, uses a min-heap to track earliest ending meeting, reuses rooms if possible, and returns the minimum number of rooms needed.

Execution Table

Step	Operation	Current Interval	Heap Before	Heap After	Visual State
1	Sort intervals	[0, 30]	[]	[]	Intervals sorted: [[0,30],[5,10],[15,20]]
2	Process interval	[0, 30]	[]	[30]	Heap: [30] (one room allocated)
3	Process interval	[5, 10]	[30]	[10,30]	Heap: [10,30] (two rooms allocated)
4	Process interval	[15, 20]	[10,30]	[20,30]	Heap: [20,30] (room freed from meeting ending at 10)

💡 All intervals processed; heap size 2 means minimum 2 rooms needed.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
intervals	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]	[[0,30],[5,10],[15,20]]
heap	[]	[30]	[10,30]	[20,30]	[20,30]
current interval	N/A	[0,30]	[5,10]	[15,20]	N/A

Key Moments - 3 Insights

Why do we sort intervals by start time before processing?

Sorting ensures we process meetings in chronological order, so we can correctly track room availability as shown in execution_table rows 1 and 2.

Why do we remove the earliest ending meeting from the heap when its end time is <= current start?

Because that room becomes free and can be reused, reducing the number of rooms needed. This is shown in step 4 where 10 <= 15, so 10 is removed.

Why do we keep the heap sorted after each insertion?

To quickly access the earliest ending meeting (heap[0]) for comparison with the next meeting's start time, as seen in heap states in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the heap state after processing interval [5,10]?

A [5,10]

B [10,30]

C [30,10]

D [30]

💡 Hint

Check the 'Heap After' column at Step 3 in execution_table.

At which step does the algorithm reuse a room by removing an end time from the heap?

A Step 4

B Step 2

C Step 3

D No reuse occurs

💡 Hint

Look for when the heap size does not increase despite processing a new interval in execution_table.

If the intervals were [[0,10],[10,20],[20,30]], what would be the minimum rooms needed?

A 3

B 2

C 1

D 0

💡 Hint

Consider that meetings end exactly when the next starts, so rooms can be reused as per concept_flow.

Concept Snapshot

Meeting Rooms Minimum Rooms Required:
- Sort intervals by start time
- Use min-heap to track earliest meeting end
- For each meeting:
  - If earliest end <= current start, reuse room (pop heap)
  - Push current end to heap
- Heap size = minimum rooms needed

Full Transcript

To find the minimum number of meeting rooms needed, first sort the meetings by their start times. Then, use a min-heap to keep track of the end times of meetings currently occupying rooms. For each meeting, check if the earliest ending meeting ends before or when the current meeting starts. If yes, that room can be reused, so remove that end time from the heap. Then add the current meeting's end time to the heap. After processing all meetings, the size of the heap tells us how many rooms are needed. This approach efficiently manages room allocation by reusing rooms whenever possible.

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