Meeting Rooms Problem Minimum Rooms Required in DSA Python - Build from Scratch

Meeting Rooms Problem Minimum Rooms Required

📖 Scenario: You are organizing meetings in a company. Each meeting has a start time and an end time. You want to find out the minimum number of meeting rooms needed so that all meetings can happen without overlapping in the same room.

🎯 Goal: Build a program that calculates the minimum number of meeting rooms required given a list of meeting time intervals.

📋 What You'll Learn

Create a list called meetings with the exact intervals: [ (0, 30), (5, 10), (15, 20) ]

Create a variable called start_times that contains the start times of all meetings sorted in ascending order

Create a variable called end_times that contains the end times of all meetings sorted in ascending order

Use two pointers start_ptr and end_ptr to traverse start_times and end_times

Create variables used_rooms and max_rooms to track current and maximum rooms needed

Implement the logic to increase used_rooms when a meeting starts before the earliest meeting ends, else decrease used_rooms

Print the final max_rooms which is the minimum number of meeting rooms required

💡 Why This Matters

🌍 Real World

Scheduling meeting rooms efficiently is important in offices to avoid conflicts and maximize resource use.

💼 Career

This problem is common in software engineering interviews and helps develop skills in sorting, two-pointer technique, and interval management.

1

Create the list of meeting intervals

Create a list called meetings with these exact tuples: (0, 30), (5, 10), and (15, 20)

DSA Python

# Create the list of meetings with exact intervals
# Your code here

Hint

Use square brackets for the list and parentheses for each tuple.

2

Extract and sort start and end times

Create a list called start_times containing the start times of all meetings sorted in ascending order, and a list called end_times containing the end times of all meetings sorted in ascending order

DSA Python

meetings = [(0, 30), (5, 10), (15, 20)]
# Create start_times and end_times lists sorted ascending
# Your code here

Hint

Use list comprehensions to extract start and end times, then sort them.

3

Implement the logic to find minimum rooms

Create variables start_ptr and end_ptr set to 0, used_rooms set to 0, and max_rooms set to 0. Use a while loop to traverse start_times while start_ptr is less than the length of start_times. Inside the loop, if start_times[start_ptr] is less than end_times[end_ptr], increase used_rooms by 1 and move start_ptr forward. Else, decrease used_rooms by 1 and move end_ptr forward. Update max_rooms to be the maximum of itself and used_rooms in each iteration.

DSA Python

meetings = [(0, 30), (5, 10), (15, 20)]
start_times = sorted([meeting[0] for meeting in meetings])
end_times = sorted([meeting[1] for meeting in meetings])
# Initialize pointers and counters
# Your code here

Hint

Use two pointers to compare start and end times and track rooms used.

4

Print the minimum number of meeting rooms required

Print the variable max_rooms which holds the minimum number of meeting rooms required

DSA Python

meetings = [(0, 30), (5, 10), (15, 20)]
start_times = sorted([meeting[0] for meeting in meetings])
end_times = sorted([meeting[1] for meeting in meetings])

start_ptr = 0
end_ptr = 0
used_rooms = 0
max_rooms = 0

while start_ptr < len(start_times):
    if start_times[start_ptr] < end_times[end_ptr]:
        used_rooms += 1
        start_ptr += 1
        max_rooms = max(max_rooms, used_rooms)
    else:
        used_rooms -= 1
        end_ptr += 1

# Print the minimum number of rooms needed
# Your code here

Hint

Use print(max_rooms) to show the result.

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 minimum number of meeting rooms needed to hold all meetings without overlap

B. The maximum duration of a single meeting

C. The total number of meetings scheduled

D. The earliest start time among all meetings

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. Final Answer:

   The minimum number of meeting rooms needed to hold all meetings without overlap -> Option A

3. Quick Check:

   Minimum rooms = rooms needed to avoid overlap [OK]

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

Common Mistakes:

• Confusing total meetings with rooms needed
• Ignoring overlapping intervals
• Counting meeting duration instead of rooms

2. Which of the following Python code snippets correctly sorts a list of meeting intervals by their start time?

easy

A. intervals.sort(key=lambda x: x[1])

B. intervals.sort(key=lambda x: x[0])

C. intervals.sort()

D. intervals.sort(key=lambda x: x)

Solution

1. Step 1: Identify sorting by start time

   Each interval is a list or tuple like [start, end]. Sorting by x[0] sorts by start time.

2. Step 2: Check other options

   Sorting by x[1] sorts by end time, sort() without key sorts lexicographically (primarily by start but also end), lambda x: x sorts by whole interval.

3. Final Answer:

   intervals.sort(key=lambda x: x[0]) -> Option B

4. Quick Check:

   Sort by start time = key=lambda x: x[0] [OK]

Hint: Sort intervals by start time using key=lambda x: x[0] [OK]

Common Mistakes:

• Sorting by end time instead of start time
• Using sort() without key on lists of lists
• Confusing lambda syntax

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

intervals = [[0, 30], [5, 10], [15, 20]]
starts = sorted([i[0] for i in intervals])
ends = sorted([i[1] for i in intervals])
rooms = 0
end_ptr = 0
for start in starts:
    if start < ends[end_ptr]:
        rooms += 1
    else:
        end_ptr += 1
print(rooms)

medium

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Sort start and end times

   starts = [0,5,15], ends = [10,20,30]. Initialize rooms=0, end_ptr=0.

2. Step 2: Trace the loop

   - start=0 < ends[0]=10: yes, rooms=1 (end_ptr=0)
   - start=5 < ends[0]=10: yes, rooms=2 (end_ptr=0)
   - start=15 < ends[0]=10: no, end_ptr=1
   Final rooms=2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Maximum concurrent meetings = 2 [OK]

Hint: Compare starts with earliest end to count rooms [OK]

Common Mistakes:

• Not moving end pointer correctly
• Counting rooms too many times
• Mixing start and end comparisons

4. The following code is intended to find the minimum number of meeting rooms needed. What is the bug?

def minMeetingRooms(intervals):
    starts = sorted([i[0] for i in intervals])
    ends = sorted([i[1] for i in intervals])
    rooms = 0
    end_ptr = 0
    for start in starts:
        if start > ends[end_ptr]:
            end_ptr += 1
        else:
            rooms += 1
    return rooms

print(minMeetingRooms([[0, 30], [5, 10], [15, 20]]))

medium

A. The comparison should be start < ends[end_ptr], not start > ends[end_ptr]

B. The ends list is not sorted

C. The rooms variable is not initialized

D. The function does not return any value

Solution

1. Step 1: Analyze the comparison logic

   The code uses if start > ends[end_ptr] to advance end_ptr, but correct logic requires advancing when start >= ends[end_ptr] (or equivalently, increment rooms when start < ends[end_ptr]).

2. Step 2: Understand impact

   Wrong comparison fails when start == ends[end_ptr], incorrectly counting extra room.

3. Final Answer:

   The comparison should be start < ends[end_ptr], not start > ends[end_ptr] -> Option A

4. Quick Check:

   Correct comparison fixes room count [OK]

Hint: Use start < ends[end_ptr] to check overlap [OK]

Common Mistakes:

• Using wrong comparison operator
• Not sorting ends list
• Forgetting to increment end pointer

5. Given the meeting intervals [[1, 4], [2, 5], [7, 9], [3, 6], [10, 11]], what is the minimum number of meeting rooms required to schedule all meetings without overlap?

hard

A. 4

B. 2

C. 1

D. 3

Solution

1. Step 1: Sort start and end times

   starts = [1,2,3,7,10], ends = [4,5,6,9,11].

2. Step 2: Simulate two-pointer algorithm

   rooms=0, end_ptr=0
   - start=1 < 4: rooms=1
   - start=2 < 4: rooms=2
   - start=3 < 4: rooms=3
   - start=7 < 4: no, end_ptr=1
   - start=10 < 5: no, end_ptr=2
   The final rooms value (3) is the max concurrent meetings needed.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max overlap (e.g., [1,4],[2,5],[3,6]) = 3 [OK]

Hint: Track overlaps by comparing starts and ends [OK]

Common Mistakes:

• Not updating end pointer correctly
• Counting all meetings as overlapping
• Ignoring meeting end times