Meeting Rooms Problem Minimum Rooms Required in DSA Java

Mental Model

We want to find the smallest number of rooms needed so that no meetings overlap in the same room.

Analogy: Imagine you have several meetings scheduled in different rooms. You want to know how many rooms you need so that no two meetings happen in the same room at the same time.

Meetings timeline:
[1,4]   [2,5]   [7,9]
Rooms needed:
Room1: [1,4] -> [7,9]
Room2:    [2,5]

Dry Run Walkthrough

Input: meetings: [[1,4], [2,5], [7,9]]

Goal: Find the minimum number of rooms needed so no meetings overlap in the same room.

Step 1: Sort meetings by start time

[1,4] -> [2,5] -> [7,9]

Why: Sorting helps us check meetings in order of when they start.

Step 2: Create a min-heap to track end times of meetings currently using rooms

Heap: []

Why: Heap helps quickly find the earliest meeting that ends.

Step 3: Add first meeting end time 4 to heap

Heap: [4]

Why: First meeting occupies one room until time 4.

Step 4: Check second meeting start 2 against earliest end time 4

Heap: [4]

Why: 2 < 4 means overlap, need new room.

Step 5: Add second meeting end time 5 to heap

Heap: [4, 5]

Why: Two meetings overlap, so two rooms needed.

Step 6: Check third meeting start 7 against earliest end time 4

Heap: [4, 5]

Why: 7 >= 4 means first room is free now.

Step 7: Remove earliest end time 4 from heap and add 9

Heap: [5, 9]

Why: Reuse room freed at time 4 for meeting starting at 7.

Result:

Heap: [5, 9]
Minimum rooms needed: 2

Annotated Code

DSA Java

import java.util.*;

public class MeetingRooms {
    public static int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;

        // Sort meetings by start time
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        // Min-heap to track earliest end time
        PriorityQueue<Integer> heap = new PriorityQueue<>();

        // Add first meeting end time
        heap.add(intervals[0][1]);

        for (int i = 1; i < intervals.length; i++) {
            // If current meeting starts after earliest ended meeting
            if (intervals[i][0] >= heap.peek()) {
                heap.poll(); // Room freed
            }
            heap.add(intervals[i][1]); // Allocate room
        }

        return heap.size(); // Number of rooms needed
    }

    public static void main(String[] args) {
        int[][] meetings = {{1,4}, {2,5}, {7,9}};
        System.out.println(minMeetingRooms(meetings));
    }
}

Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

Sort meetings by start time to process in order

PriorityQueue<Integer> heap = new PriorityQueue<>();

Create min-heap to track earliest meeting end times

heap.add(intervals[0][1]);

Add first meeting end time to heap, occupying one room

if (intervals[i][0] >= heap.peek()) {

If current meeting starts after earliest ended meeting, free that room

heap.poll();

Remove earliest ended meeting from heap to reuse room

heap.add(intervals[i][1]);

Add current meeting end time to heap, allocating room

return heap.size();

Number of rooms needed equals heap size

Output

2

Complexity Analysis

Time: O(n log n) because we sort the meetings and then insert/remove from a heap for each meeting

Space: O(n) because in worst case all meetings overlap and all end times are stored in the heap

vs Alternative: A naive approach checks all pairs for overlap O(n^2), this heap method is more efficient

Edge Cases

empty meetings array

returns 0 rooms needed

DSA Java

if (intervals == null || intervals.length == 0) return 0;

all meetings non-overlapping

returns 1 room needed

DSA Java

if (intervals[i][0] >= heap.peek()) { heap.poll(); }

all meetings fully overlapping

returns number of meetings as rooms needed

DSA Java

heap.add(intervals[i][1]);

When to Use This Pattern

When you see a problem asking for minimum rooms or resources to schedule overlapping intervals, use a min-heap to track earliest finishing times and allocate rooms efficiently.

Common Mistakes

Mistake: Not sorting meetings by start time before processing
Fix: Sort intervals by start time first to process in chronological order

Mistake: Not reusing rooms by removing ended meetings from heap
Fix: Check if current meeting starts after earliest ended meeting and remove it from heap to reuse room

Summary

Finds the minimum number of rooms needed so no meetings overlap in the same room.

Use when scheduling overlapping intervals and you want to minimize resources like rooms.

Sort meetings by start time and use a min-heap to track earliest end times to efficiently allocate rooms.

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