Meeting Rooms Problem Minimum Rooms Required in DSA Javascript - 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 into heap

↓

Repeat for all intervals

↓

Heap size = minimum rooms needed

Sort intervals by start time, then use a min-heap to track end times of ongoing meetings. For each meeting, if a room is free (earliest end time <= current start), reuse it; else add a new room. The heap size at the end is the minimum rooms required.

Execution Sample

DSA Javascript

const intervals = [[0,30],[5,10],[15,20]];
intervals.sort((a,b) => a[0] - b[0]);
const heap = [];
for (const [start, end] of intervals) {
  if (heap.length && heap[0] <= start) heap.shift();
  heap.push(end);
  heap.sort((a,b) => a-b);
}
console.log(heap.length);

Sort intervals by start time, then iterate to allocate rooms using a min-heap of end times, printing the minimum rooms needed.

Execution Table

Step	Operation	Current Interval	Heap Before	Heap After	Rooms Needed
1	Sort intervals	[0,30]	[]	[]	0
2	Process interval	[0,30]	[]	[30]	1
3	Process interval	[5,10]	[30]	[10,30]	2
4	Process interval	[15,20]	[10,30]	[20,30]	2
5	Check earliest end <= start	[15,20]	[10,30]	[20,30]	2
6	Final rooms needed	N/A	[20,30]	[20,30]	2

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

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	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]]	[[0,30],[5,10],[15,20]]
heap	[]	[30]	[10,30]	[20,30]	[20,30]	[20,30]
rooms_needed	0	1	2	2	2	2

Key Moments - 3 Insights

Why do we sort intervals by start time first?

Sorting ensures we process meetings in the order they begin, so we can allocate rooms correctly as time moves forward (see Step 1 in execution_table).

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

Because that room is now free before the current meeting starts, so we can reuse it instead of adding a new room (see Step 5 in execution_table).

Why do we keep the heap sorted after each insertion?

To quickly find the earliest finishing meeting (smallest end time) at the top of the heap for efficient room reuse checks (see heap states in execution_table).

Visual Quiz - 3 Questions

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

A [10]

B [5, 10]

C [10,30]

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 5

B Step 4

C Step 2

D Step 3

💡 Hint

Look for when the heap changes by removing an end time before adding the current interval's end time.

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

A 2

B 1

C 3

D 0

💡 Hint

Check variable_tracker for how heap size relates to rooms needed.

Concept Snapshot

Meeting Rooms Minimum Rooms Required:
1. Sort intervals by start time.
2. Use a min-heap to track meeting end times.
3. For each meeting, if earliest end <= current start, reuse room (pop heap).
4. Push current meeting end time.
5. Heap size after all intervals = minimum rooms needed.

Full Transcript

To find the minimum number of meeting rooms needed, first sort all meeting intervals by their start times. Then, use a min-heap to keep track of the end times of meetings currently using rooms. For each meeting, check if the earliest finishing 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. The size of the heap after processing all meetings tells us the minimum number of rooms required. This approach efficiently manages room allocation by always reusing rooms that free up earliest.

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