Meeting Rooms Problem Minimum Rooms Required in DSA Javascript - 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 schedule all given meetings without overlap.

beginner

How do you determine if two meetings overlap?

Two meetings overlap if the start time of one meeting is less than the end time of the other meeting.

intermediate

Why do we sort meetings by their start time in this problem?

Sorting by start time helps us process meetings in order and efficiently check for overlaps to allocate rooms.

intermediate

What data structure is commonly used to track ongoing meetings and their end times?

A min-heap (priority queue) is used to keep track of the earliest finishing meeting to reuse rooms efficiently.

intermediate

Explain the step when a meeting room can be reused in the algorithm.

If the current meeting's start time is greater than or equal to the earliest ending meeting's end time, that room can be reused by removing the earliest meeting from the heap.

What is the first step in solving the Meeting Rooms Minimum Rooms Required problem?

A Sort meetings by start time

B Sort meetings by end time

C Use a stack to store meetings

D Count total meetings

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

Which data structure helps efficiently find the earliest finishing meeting?

A Queue

B Array

C Min-heap

D Stack

A min-heap keeps the smallest end time at the top, helping to track room availability.

When can a meeting room be reused for a new meeting?

A When the new meeting starts before the earliest meeting ends

B When the new meeting starts after the earliest meeting ends

C When the new meeting ends before the earliest meeting starts

D When the new meeting overlaps with all meetings

A room is free if the new meeting starts at or after the earliest meeting ends.

What does the size of the min-heap represent during the algorithm?

A Number of meetings processed

B Total meetings

C Number of overlapping meetings

D Number of rooms currently in use

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

What is the final answer to the Meeting Rooms Minimum Rooms Required problem?

A Maximum size of the min-heap during processing

B Total number of meetings

C Minimum start time

D Sum of all meeting durations

The maximum number of rooms used at once is the minimum rooms required.

Describe the step-by-step approach to find the minimum number of meeting rooms required.

Think about sorting, tracking ongoing meetings, and reusing rooms.

Explain why a min-heap is preferred over other data structures in this problem.

Focus on how to quickly find the meeting that ends soonest.

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 minimum number of meeting rooms needed so no meetings overlap

B. The maximum length of a single meeting

C. The total number of meetings scheduled

D. The earliest meeting start time

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Clarify what is being counted

   We count how many meetings happen at the same time to find the minimum rooms needed.

3. Final Answer:

   The minimum number of meeting rooms needed so no meetings overlap -> Option A

4. Quick Check:

   Minimum rooms = max overlapping meetings [OK]

Hint: Count max overlapping intervals to find rooms needed [OK]

Common Mistakes:

• Confusing total meetings with rooms needed
• Ignoring overlapping times
• Thinking earliest start time is the answer

2. Which of the following JavaScript code snippets correctly sorts an array of meeting intervals by their start time? Assume intervals is an array of objects with 'start' and 'end' properties.

easy

A. intervals.sort((a, b) => b.end - a.end);

B. intervals.sort((a, b) => b.start - a.start);

C. intervals.sort((a, b) => a.end - b.end);

D. intervals.sort((a, b) => a.start - b.start);

Solution

1. Step 1: Identify sorting by start time

   We want to sort intervals by their start property in ascending order.

2. Step 2: Check the sort function

   The comparator (a, b) => a.start - b.start sorts ascending by start time.

3. Final Answer:

   intervals.sort((a, b) => a.start - b.start); -> Option D

4. Quick Check:

   Ascending start time sort = intervals.sort((a, b) => a.start - b.start); [OK]

Hint: Sort intervals by start ascending: (a,b) => a.start - b.start [OK]

Common Mistakes:

• Sorting by end time instead of start
• Sorting descending when ascending needed
• Using incorrect comparator syntax

3. What is the minimum number of meeting rooms required for the following intervals?
const intervals = [{start: 0, end: 30}, {start: 5, end: 10}, {start: 15, end: 20}];

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Analyze overlapping intervals

   Meetings: [0-30], [5-10], [15-20]. The first overlaps with the second and third.

2. Step 2: Count max overlaps

   At time 5-10, two meetings overlap (0-30 and 5-10). At 15-20, two meetings overlap (0-30 and 15-20). Max overlap is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max overlapping meetings = 2 rooms needed [OK]

Hint: Find max overlaps by checking intervals start and end times [OK]

Common Mistakes:

• Counting total meetings instead of overlaps
• Assuming 3 rooms because 3 meetings exist
• Ignoring overlap intervals

4. The following code attempts to find the minimum number of meeting rooms needed but has a bug. What is the bug?

function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a.start - b.start);
  let rooms = [];
  for (let meeting of intervals) {
    if (rooms.length === 0 || meeting.start < rooms[rooms.length - 1]) {
      rooms.push(meeting.end);
    } else {
      rooms[rooms.length - 1] = meeting.end;
    }
  }
  return rooms.length;
}

medium

A. It returns the wrong value (should return rooms array)

B. It sorts intervals by end time instead of start time

C. It compares meeting.start with a number incorrectly (rooms array stores end times, but comparison is wrong)

D. It uses push instead of unshift on rooms array

Solution

1. Step 1: Understand rooms array usage

   Rooms array stores end times of meetings currently occupying rooms.

2. Step 2: Check comparison logic

   Comparing meeting.start with rooms[rooms.length - 1] (last end time) is incorrect because rooms should be a min-heap or sorted structure, not just last element.

3. Final Answer:

   It compares meeting.start with a number incorrectly (rooms array stores end times, but comparison is wrong) -> Option C

4. Quick Check:

   Incorrect comparison of start with last end time causes bug [OK]

Hint: Use a min-heap or sorted structure for end times, not last element [OK]

Common Mistakes:

• Comparing start with last end time without sorting
• Not using a priority queue for room end times
• Returning wrong variable

5. Given the intervals [[1,4],[2,5],[7,9],[6,10],[8,11]], what is the minimum number of meeting rooms required? Explain your reasoning.

hard

A. 3

B. 2

C. 4

D. 5

Solution

1. Step 1: Sort intervals by start time

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

2. Step 2: Track overlapping meetings

   Between 1-5, two meetings overlap ([1,4] and [2,5]). Between 6-11, three meetings overlap ([6,10], [7,9], [8,11]). Max overlap is 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Max overlapping meetings = 3 rooms needed [OK]

Hint: Find max overlaps by checking intervals start and end times carefully [OK]

Common Mistakes:

• Not sorting intervals before checking overlaps
• Counting total meetings instead of max overlaps
• Missing overlaps in later intervals