Meeting Rooms Problem Minimum Rooms Required in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort the intervals by their start time.

DSA Java

Arrays.sort(intervals, (a, b) -> a[1]b);

Drag options to blanks, or click blank then click option'

A.end - b.end

B.end + b.end

C.start + b.start

D.start - b.start

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by end time instead of start time.

Using addition instead of subtraction in comparator.

Sorting intervals by their start time helps to process meetings in chronological order.

2fill in blank

medium

Complete the code to initialize a priority queue that sorts by interval end time.

DSA Java

PriorityQueue<Interval> pq = new PriorityQueue<>((a, b) -> a[1]b);

Drag options to blanks, or click blank then click option'

A.end - b.end

B.end + b.end

C.start - b.start

D.start + b.start

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting priority queue by start time instead of end time.

Using addition instead of subtraction in comparator.

The priority queue should order intervals by their end time to track earliest finishing meeting.

3fill in blank

hard

Fix the error in the condition to check if the current meeting can reuse a room.

DSA Java

if (intervals[i].start [1] pq.peek().end) { pq.poll(); }

Drag options to blanks, or click blank then click option'

A>=

B<=

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than or less than or equal to instead of greater than or equal to.

Not polling the priority queue when reusing a room.

If the current meeting starts at or after the earliest ending meeting, we can reuse that room.

4fill in blank

hard

Fill both blanks to add the current interval to the priority queue and return the size as minimum rooms.

DSA Java

pq.[1](intervals[i]);
return pq.[2]();

Drag options to blanks, or click blank then click option'

Aadd

Bsize

Cpoll

Dpeek

Attempts:

3 left

💡 Hint

Common Mistakes

Using poll or peek instead of add to insert.

Using peek instead of size to get count.

Add the current interval to the queue and return the queue size as the minimum rooms needed.

5fill in blank

hard

Fill all three blanks to complete the loop that processes all intervals starting from the second one.

DSA Java

for (int i = [1]; i [2] intervals.length; i[3]) {
    // process intervals
}

Drag options to blanks, or click blank then click option'

A1

B<

C++

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Starting loop from 0 instead of 1.

Using <= instead of < in loop condition.

Using i-- instead of i++.

Start from index 1, loop while i is less than length, and increment i by 1 each time.

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