Meeting Rooms II

Medium

Netflix

29 views

Topics:

ArraysGreedy AlgorithmsDynamic ProgrammingStacks

You are given an array of meeting time intervals consisting of start and end times intervals = [[start1, end1], [start2, end2], ...] where starti < endi. Your task is to determine the minimum number of meeting rooms required to host all the meetings.

For example:

Given intervals = [[0,30],[5,10],[15,20]], the output should be 2. There are three meetings. The first meeting starts at time 0 and ends at time 30. The second meeting starts at time 5 and ends at time 10. The third meeting starts at time 15 and ends at time 20. The first and second meetings overlap (from time 5 to 10), so they cannot use the same room. The first and third meetings overlap (from time 15 to 20), so they cannot use the same room. However, the second and third meetings do not overlap. Therefore, two meeting rooms are sufficient.
Given intervals = [[7,10],[2,4]], the output should be 1. The meetings do not overlap and thus can share a meeting room.
Given intervals = [[1,10],[2,7],[3,19],[8,12],[10,20],[11,30]], the output should be 4.

Consider the following edge cases:

What happens when the input array is empty? What should be the return value?
What happens if the meetings have the same start time? How does your algorithm handle that?
What happens if a meeting has zero duration (start time equals end time)?

Meeting Rooms II

Medium

Netflix

29 views

Topics:

ArraysGreedy AlgorithmsDynamic ProgrammingStacks

You are given an array of meeting time intervals consisting of start and end times intervals = [[start1, end1], [start2, end2], ...] where starti < endi. Your task is to determine the minimum number of meeting rooms required to host all the meetings.

For example:

Given intervals = [[0,30],[5,10],[15,20]], the output should be 2. There are three meetings. The first meeting starts at time 0 and ends at time 30. The second meeting starts at time 5 and ends at time 10. The third meeting starts at time 15 and ends at time 20. The first and second meetings overlap (from time 5 to 10), so they cannot use the same room. The first and third meetings overlap (from time 15 to 20), so they cannot use the same room. However, the second and third meetings do not overlap. Therefore, two meeting rooms are sufficient.
Given intervals = [[7,10],[2,4]], the output should be 1. The meetings do not overlap and thus can share a meeting room.
Given intervals = [[1,10],[2,7],[3,19],[8,12],[10,20],[11,30]], the output should be 4.

Consider the following edge cases:

What happens when the input array is empty? What should be the return value?
What happens if the meetings have the same start time? How does your algorithm handle that?
What happens if a meeting has zero duration (start time equals end time)?

Solution

Clarifying Questions

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:

What is the range of values for the start and end times of the meetings?
Can the input array `intervals` be empty or null?
Are the meeting intervals guaranteed to be valid, meaning `start_i` is always less than or equal to `end_i`?
Can meeting intervals overlap (i.e., can two meetings have the same start or end time)?
If the input array is empty, should I return 0?

Brute Force Solution

Approach

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:

Start with one meeting room.
Try to schedule each meeting in that single room. If any meetings overlap, it doesn't work.
If the first attempt fails, try two meeting rooms.
Assign the first meeting to the first room. Then, try assigning the second meeting to either the first or second room, checking for overlaps.
Continue assigning meetings to rooms, trying every possible combination of rooms for each meeting and always checking for overlaps.
If you find a valid arrangement with a certain number of rooms, remember that number. Then continue to explore if a smaller number of rooms would also work.
The smallest number of rooms that allows all meetings to be scheduled without overlaps is the answer.

Code Implementation

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

Big(O) Analysis

Time Complexity

O(n!) – The brute force algorithm explores all possible room assignments for each meeting. For n meetings, the first meeting has 1 choice of room, the second meeting has 2 choices (either room 1 or a new room 2), the third meeting has 3 choices, and so on. This results in 1 * 2 * 3 * ... * n possible combinations of room assignments. Therefore, the time complexity is O(n!), representing the factorial of the number of meetings.

Space Complexity

O(N!) – The brute force approach explores every possible room assignment for each meeting. In the worst-case scenario, for N meetings, the number of possible assignments grows factorially. The algorithm implicitly stores the current arrangement of meetings in rooms, which can potentially represent all permutations and combinations. This implicit storage of assignments dominates the space complexity, growing super-exponentially. Since the number of potential arrangements can approach N!, the space complexity is O(N!).

Optimal Solution

Approach

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:

Imagine all the meeting start times and end times are separate events, and we sort them chronologically.
Every time a meeting starts, we need a new room, so we increase our 'room count'.
Every time a meeting ends, a room becomes available, so we decrease our 'room count'.
As we go through the sorted list of start and end times, we keep track of the maximum 'room count' we ever reach. This maximum value is the minimum number of rooms needed.

Code Implementation

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

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the start and end times, where n is the number of intervals. Sorting algorithms like merge sort or quicksort typically have a time complexity of O(n log n). Iterating through the sorted start and end times to track the room count takes O(n) time. Since O(n log n) is greater than O(n), the overall time complexity is determined by the sorting step, resulting in O(n log n).

Space Complexity

O(N) – The space complexity is determined by the creation of two new lists: one for start times and one for end times. Each of these lists contains N elements, where N is the number of intervals (meetings). Therefore, we allocate auxiliary space proportional to the input size to store these start and end times. This results in a space complexity of O(N).

Edge Cases

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.