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

intermediate

Which data structure is commonly used to keep track of ongoing meetings in the Meeting Rooms Problem?

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

beginner

Why do we sort the meetings by their start time in the Meeting Rooms Problem?

Sorting by start time helps process meetings in chronological order, making it easier to allocate rooms as meetings begin.

intermediate

What does it mean if the start time of the current meeting is greater than or equal to the earliest finishing meeting in the min-heap?

It means a room has become free, so we can reuse that room for the current meeting by removing the earliest finishing meeting from the heap.

beginner

How do you determine the minimum number of rooms required after processing all meetings?

The maximum size of the min-heap during processing represents the minimum number of rooms required.

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

A Use a stack to store meetings

B Sort meetings by end time

C Sort meetings by start time

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 Min-heap (priority queue)

C Stack

D HashMap

A min-heap keeps the earliest finishing meeting at the top for quick access.

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

A Reuse the freed room by removing the earliest finishing meeting from the heap

B Add a new room

C Ignore the meeting

D Sort meetings again

Reusing the freed room avoids allocating unnecessary extra rooms.

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

A Number of overlapping meetings

B Total meetings

C Maximum meeting duration

D Minimum rooms required

The maximum heap size shows the peak number of rooms occupied simultaneously, which is the minimum needed.

Why can't we just count overlapping meetings to find the minimum rooms?

A Because some meetings do not overlap simultaneously and can share rooms

B Because counting is slow

C Because meetings always overlap

D Because meetings can be rearranged

Some meetings overlap partially, so careful allocation is needed to minimize rooms.

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

Think about how sorting and a min-heap help manage overlapping meetings.

Describe how a min-heap helps optimize the allocation of meeting rooms in the Meeting Rooms Problem.

Focus on how the min-heap stores end times and helps manage room availability.

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