Meeting Rooms Problem Minimum Rooms Required in DSA Java - Time & Space Complexity

Time Complexity: Meeting Rooms Problem Minimum Rooms Required

O(n log n)

Understanding Time Complexity

We want to find out how the time needed to find the minimum number of meeting rooms grows as the number of meetings increases.

How does the program's work change when we have more meetings to schedule?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import java.util.*;

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

This code sorts meetings by start time and uses a priority queue to track end times, finding the minimum rooms needed.

Identify Repeating Operations

• Primary operation: Looping through all meetings once after sorting.
• How many times: Once for each meeting (n times).
• Additional operation: Each insertion and removal from the priority queue happens up to n times.

How Execution Grows With Input

As the number of meetings grows, sorting takes more time, and managing the priority queue grows too.

Input Size (n)	Approx. Operations
10	About 10 log 10 + 10 operations
100	About 100 log 100 + 100 operations
1000	About 1000 log 1000 + 1000 operations

Pattern observation: The time grows a bit faster than just the number of meetings because of sorting and priority queue operations, which involve logarithms.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the number of meetings because sorting and managing the priority queue take extra steps.

Common Mistake

[X] Wrong: "The solution runs in simple linear time O(n) because it just loops through meetings once."

[OK] Correct: Sorting the meetings and using a priority queue both add extra work that grows with n log n, not just n.

Interview Connect

Understanding how sorting and priority queues affect time helps you explain your solution clearly and shows you know how to handle growing input efficiently.

Self-Check

"What if the meetings were already sorted by start time? How would that change the time complexity?"

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