Meeting Rooms Problem Minimum Rooms Required in DSA Java - 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 min-heap top end time <= current start?

↓

Pop min-heap

↓

Push current end time

↓

Repeat for all intervals

↓

Heap size = minimum rooms needed

Sort meetings by start time, use a min-heap to track end times of ongoing meetings, reuse rooms if possible, heap size gives minimum rooms.

Execution Sample

DSA Java

int minMeetingRooms(int[][] intervals) {
  Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
  PriorityQueue<Integer> heap = new PriorityQueue<>();
  for (int[] interval : intervals) {
    if (!heap.isEmpty() && heap.peek() <= interval[0]) heap.poll();
    heap.add(interval[1]);
  }
  return heap.size();
}

Sort intervals, use min-heap to track earliest ending meeting, reuse room if possible, return heap size as minimum rooms.

Execution Table

Step	Operation	Current Interval	Heap Top (Earliest End)	Heap After Operation	Visual State (Heap)
1	Sort intervals	[0, 30], [5, 10], [15, 20]	-	-	[ ]
2	Process interval	[0, 30]	-	[30]	[30]
3	Process interval	[5, 10]	30	[30, 10]	[10, 30]
4	Check if earliest end <= current start	[5, 10]	30	No pop	[30, 10]
5	Process interval	[15, 20]	10	[30, 20]	[20, 30]
6	Check if earliest end <= current start	[15, 20]	10	Pop 10	[30]
7	Add current end	[15, 20]	-	[30, 20]	[20, 30]
8	End of intervals	-	-	-	Heap size = 2 (minimum rooms)

💡 All intervals processed; heap size indicates minimum rooms required.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 5	After Step 7	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]
heap size	0	1	2	2	2	2

Key Moments - 3 Insights

Why do we pop from the heap only if the earliest end time is less or equal to the current start time?

Because if the earliest meeting ends before the current meeting starts, that room can be reused. This is shown in execution_table rows 6 and 7 where we pop 10 before adding 20.

Why does the heap size represent the minimum number of rooms needed?

The heap stores end times of ongoing meetings. Its size shows how many meetings overlap at once, meaning how many rooms are occupied simultaneously, as seen in the final heap size in row 8.

Why do we sort intervals by start time before processing?

Sorting ensures we process meetings in chronological order, so we can correctly track room usage over time. This is the first step in the flow and execution_table row 1.

Visual Quiz - 3 Questions

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

A [10, 30]

B [5, 10]

C [30]

D [30, 10]

💡 Hint

Check the 'Heap After Operation' and 'Visual State' columns at Step 3.

At which step does the algorithm pop an end time from the heap?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look for 'Pop' action in the 'Operation' column in execution_table.

If the interval [15, 20] started at 31 instead, how would the heap size change after processing it?

A Heap size would increase to 3

B Heap size would remain 2

C Heap size would decrease to 1

D Heap would be empty

💡 Hint

Consider that if the current start is after earliest end, the heap pops one end time before adding new.

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)
  - Add current meeting end to heap
- Heap size = minimum rooms needed

Full Transcript

This visualization shows how to find the minimum number of meeting rooms needed for given intervals. First, intervals are sorted by start time. Then, a min-heap tracks the earliest ending meeting currently occupying a room. For each meeting, if the earliest meeting ends before or when the current meeting starts, that room is reused by popping from the heap. The current meeting's end time is added to the heap. The heap size after processing all intervals represents the minimum rooms required. The execution table traces each step, showing heap changes and decisions. Key moments clarify why popping happens only when possible reuse occurs, why sorting is essential, and why heap size equals rooms needed. The quiz tests understanding of heap state and operations during execution.

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 earliest meeting start time

B. The minimum number of meeting rooms needed so no meetings overlap

C. The total number of meetings scheduled

D. The maximum length of a single meeting

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Clarify what is being counted

   We count rooms, not meetings or times. The goal is to avoid overlap in any single room.

3. Final Answer:

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

4. Quick Check:

   Minimum rooms = no overlapping meetings [OK]

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

Common Mistakes:

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

2. Which Java data structure is best to track ongoing meetings by their end times when solving the Meeting Rooms problem?

easy

A. HashMap

B. ArrayList

C. Stack

D. PriorityQueue (Min-Heap)

Solution

1. Step 1: Identify the need to track earliest ending meeting

   We need to quickly find the meeting that ends earliest to reuse its room if possible.

2. Step 2: Choose data structure supporting quick min extraction

   A PriorityQueue (Min-Heap) efficiently gives the earliest end time meeting.

3. Final Answer:

   PriorityQueue (Min-Heap) -> Option D

4. Quick Check:

   Min-heap tracks earliest end time [OK]

Hint: Use min-heap to track earliest meeting end [OK]

Common Mistakes:

• Using HashMap which doesn't order by end time
• Using Stack which is LIFO, not suitable here
• Using ArrayList without sorting or heap

3. What is the output of the following Java code snippet that calculates minimum meeting rooms needed?

int[][] intervals = {{0, 30}, {5, 10}, {15, 20}};
System.out.println(minMeetingRooms(intervals));

public static int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int[] interval : intervals) {
        if (!heap.isEmpty() && heap.peek() <= interval[0]) {
            heap.poll();
        }
        heap.add(interval[1]);
    }
    return heap.size();
}

medium

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Sort intervals by start time

   Sorted intervals: [0,30], [5,10], [15,20]

2. Step 2: Use min-heap to track end times and count rooms

   - Add 30 to heap - Next interval starts at 5, 5 < 30, add 10 to heap (2 rooms) - Next interval starts at 15, 15 > 10, remove 10, add 20 (still 2 rooms) Heap size = 2

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Overlaps require 2 rooms [OK]

Hint: Sort by start, use min-heap for end times [OK]

Common Mistakes:

• Not sorting intervals before processing
• Not removing ended meetings from heap
• Counting total meetings instead of rooms

4. Find the bug in this Java code for minimum meeting rooms:

public static int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    for (int[] interval : intervals) {
        if (!heap.isEmpty() && heap.peek() <= interval[0]) {
            heap.poll();
        }
        heap.add(interval[1]);
    }
    return heap.size();
}

medium

A. Sorting intervals by end time instead of start time

B. Using PriorityQueue instead of Stack

C. Not checking if heap is empty before peek

D. Adding interval start time instead of end time to heap

Solution

1. Step 1: Check sorting criteria

   The code sorts intervals by end time, but we must sort 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 correctly, causing wrong room count.

3. Final Answer:

   Sorting intervals by end time instead of start time -> Option A

4. Quick Check:

   Sort by start time, not end time [OK]

Hint: Sort intervals by start time before processing [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Ignoring heap empty check (though code does it here)
• Adding wrong values to heap

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

hard

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Sort intervals by start time

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

2. Step 2: Track rooms using min-heap of end times

   - Add 4 (heap=[4], 1 room) - 2 < 4 (peek=4 > 2), add 5 (heap=[4,5], 2 rooms) - 6 >= 4 (peek=4 <= 6), poll 4, add 8 (heap=[5,8], 2 rooms) - 7 >= 5 (peek=5 <= 7), poll 5, add 9 (heap=[8,9], 2 rooms) - 9 >= 8 (peek=8 <= 9), poll 8, add 10 (heap=[9,10], 2 rooms) Heap size = 2 (max was 2)

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Max overlaps = 2 rooms needed [OK]

Hint: Count max overlaps after sorting by start time [OK]

Common Mistakes:

• Not sorting intervals before processing
• Miscounting overlaps at 7 and 9
• Assuming 1 room is enough