You are given a list of meeting time intervals, where each interval consists of a start time and an end time. Your task is to determine the minimum number of conference rooms required to accommodate all the meetings without any overlap. Assume that a meeting room can be reused immediately after a meeting ends.
Example 1:
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Explanation: Two conference rooms are required.
Example 2:
Input: [[7,10],[2,4]]
Output: 1
Explanation: One conference room is sufficient since the meetings do not overlap.
Example 3:
Input: [[1,8],[6,20],[9,16],[13,17]]
Output: 3
Write a function that takes the array of meeting intervals as input and returns the minimum number of conference rooms required.
When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force way to figure out how many meeting rooms you need is to try every possible room assignment. We assign meetings to rooms one by one, checking for conflicts along the way. This process continues until all meetings have been assigned.
Here's how the algorithm would work step-by-step:
def meeting_rooms_brute_force(intervals):
number_of_intervals = len(intervals)
for number_of_rooms in range(1, number_of_intervals + 1):
def can_schedule(room_assignments):
# Check if the proposed arrangement is valid
for first_interval_index in range(number_of_intervals):
for second_interval_index in range(first_interval_index + 1, number_of_intervals):
if room_assignments[first_interval_index] == room_assignments[second_interval_index]:
interval_one_start = intervals[first_interval_index][0]
interval_one_end = intervals[first_interval_index][1]
interval_two_start = intervals[second_interval_index][0]
interval_two_end = intervals[second_interval_index][1]
if not (interval_one_end <= interval_two_start or interval_two_end <= interval_one_start):
return False
return True
def find_arrangement(index, room_assignments):
if index == number_of_intervals:
return can_schedule(room_assignments)
for room in range(number_of_rooms):
room_assignments[index] = room
# Try to schedule this arrangement
if find_arrangement(index + 1, room_assignments):
return True
return False
room_assignments = [0] * number_of_intervals
#If a valid arrangement is found, return the number of rooms.
if find_arrangement(0, room_assignments):
return number_of_rooms
return number_of_intervals #Should never reach here because rooms <= intervals
The most efficient way to determine the minimum number of meeting rooms needed is to focus on when meetings start and end. Instead of checking every possible room arrangement, we track the current demand at any given moment.
Here's how the algorithm would work step-by-step:
def min_meeting_rooms(intervals):
start_times = sorted([interval[0] for interval in intervals])
end_times = sorted([interval[1] for interval in intervals])
rooms_needed = 0
max_rooms_needed = 0
start_index = 0
end_index = 0
while start_index < len(intervals):
# If a meeting starts before another ends, we need a new room
if start_times[start_index] < end_times[end_index]:
rooms_needed += 1
# Update max rooms needed so far
max_rooms_needed = max(max_rooms_needed, rooms_needed)
start_index += 1
else:
# Meeting has ended, so free up a room
rooms_needed -= 1
end_index += 1
return max_rooms_needed
Case | How to Handle |
---|---|
Empty input array | Return 0 as no meeting rooms are needed when there are no meetings. |
Null input array | Throw an IllegalArgumentException or return 0 after a null check to indicate invalid input. |
Single meeting interval | Return 1 as only one meeting room is required. |
Meetings with identical start and end times (zero-length meetings) | The algorithm should treat these as valid meetings and not cause any errors in calculating room requirements. |
Meetings with overlapping intervals covering the entire timeline | The algorithm correctly identifies maximum overlap and allocates rooms accordingly. |
Meetings sorted by start time, resulting in continuously increasing end times. | The algorithm correctly identifies that only one room is needed as meetings are scheduled serially. |
Large number of meeting intervals that could cause integer overflow in calculations (e.g., if using number of milliseconds since epoch) | Use data types with sufficient range to handle the largest possible time values (e.g., long instead of int for timestamps) and avoid arithmetic operations that could overflow. |
Meeting intervals with very large or very small start/end times. | Confirm data types (e.g., int vs long) are appropriate for the magnitude of the interval values to avoid truncation or overflow issues. |