Meeting Rooms Problem Minimum Rooms Required in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Meeting Rooms Problem Minimum Rooms Required?

To find the minimum number of meeting rooms needed to hold all meetings without any overlap.

beginner

In the Meeting Rooms Problem, why do we sort the meetings by their start time?

Sorting by start time helps us process meetings in the order they begin, making it easier to check for overlaps and allocate rooms efficiently.

intermediate

What data structure is commonly used to track the end times of meetings currently occupying rooms?

A min-heap (priority queue) is used to keep track of the earliest finishing meeting, so we can reuse rooms as soon as they become free.

intermediate

Explain the process of allocating rooms when a new meeting starts in the Meeting Rooms Problem.

If the new meeting starts after or when the earliest meeting ends (top of min-heap), we reuse that room by updating the end time. Otherwise, we allocate a new room by adding the meeting's end time to the heap.

beginner

What does the maximum size of the min-heap represent during processing all meetings?

It represents the minimum number of rooms required to hold all meetings without overlap.

Why do we use a min-heap in the Meeting Rooms Problem?

A To store all meeting start times

B To sort meetings by start time

C To quickly find the meeting that ends earliest

D To count total meetings

The min-heap helps us find the earliest finishing meeting to decide if a room can be reused.

What is the first step before allocating rooms in the Meeting Rooms Problem?

A Sort meetings by their end time

B Count overlapping meetings

C Add all meetings to a heap

D Sort meetings by their start time

Sorting meetings by start time allows us to process them in chronological order.

If a meeting starts after the earliest meeting ends, what should we do?

A Ignore the meeting

B Reuse the room of the earliest meeting

C Allocate a new room

D End all meetings

We can reuse the room because it becomes free when the earliest meeting ends.

What does the number of elements in the min-heap represent during processing?

A Number of rooms currently in use

B Number of meetings starting soon

C Number of meetings processed

D Number of meetings finished

The min-heap size shows how many rooms are occupied at that moment.

What is the time complexity of the Meeting Rooms Problem solution using a min-heap?

A O(n log n)

B O(n^2)

C O(n)

D O(log n)

Sorting takes O(n log n) and each meeting is pushed and popped from the heap in O(log n), so overall O(n log n).

Describe step-by-step how to find the minimum number of meeting rooms required given a list of meeting intervals.

Think about sorting first, then how to track room availability.

Explain why a min-heap is preferred over other data structures for tracking meeting end times in this problem.

Focus on how quickly we can find the earliest finishing meeting.

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