Meeting Rooms III

Hard

1 view

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [start_i, end_i] means that a meeting will be held during the half-closed time interval [start_i, end_i). All the values of start_i are unique.

Meetings are allocated to rooms in the following manner:

Each meeting will take place in the unused room with the lowest number.
If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

A half-closed interval [a, b) is the interval between a and b including a and not including b.

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.

Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.

Constraints:

1 <= n <= 100
1 <= meetings.length <= 10⁵
meetings[i].length == 2
0 <= start_i < end_i <= 5 * 10⁵
All the values of start_i are unique.

Meeting Rooms III

Hard

1 view

Topics:

ArraysGreedy AlgorithmsDynamic Programming

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [start_i, end_i] means that a meeting will be held during the half-closed time interval [start_i, end_i). All the values of start_i are unique.

Meetings are allocated to rooms in the following manner:

Each meeting will take place in the unused room with the lowest number.
If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.
When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.

A half-closed interval [a, b) is the interval between a and b including a and not including b.

Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0.

Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1.

Constraints:

1 <= n <= 100
1 <= meetings.length <= 10⁵
meetings[i].length == 2
0 <= start_i < end_i <= 5 * 10⁵
All the values of start_i are unique.

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 are the constraints on the size of the `meetings` array and the values of `starti` and `endi`? Specifically, what are the maximum possible values?
Can meeting times overlap, or can a meeting's `endi` be equal to another meeting's `starti`?
What should I return if the `meetings` array is empty?
If multiple rooms have the same maximum number of meetings, how should I handle ties? (The prompt mentions returning the smallest room number in such cases, but I want to confirm.)
Is `starti` always strictly less than `endi` for each meeting?

Brute Force Solution

Approach

The problem involves figuring out which room is used the most when many meetings are scheduled. The brute force solution involves simulating every meeting one by one to see which room is used the most.

Here's how the algorithm would work step-by-step:

For each meeting, go through each room to see if it's available during that time.
If a room is available (meaning no other meeting is happening there at that exact time), assign the meeting to that room.
If multiple rooms are available, assign the meeting to the first available room.
Keep track of how many times each room is used.
After considering all the meetings, find the room that was used the most often.
That room is the one that hosted the most meetings.

Code Implementation

def most_booked_meeting_room_brute_force(number_of_rooms, meetings):
    rooms_usage_count = [0] * number_of_rooms
    rooms_availability = [[] for _ in range(number_of_rooms)]

    for meeting_start, meeting_end in meetings:

        room_found = False
        for room_index in range(number_of_rooms):
            is_available = True

            #Check if the room is available for the current meeting time
            for booked_meeting_start, booked_meeting_end in rooms_availability[room_index]:
                if not (meeting_end <= booked_meeting_start or meeting_start >= booked_meeting_end):
                    is_available = False
                    break

            if is_available:

                #Assign the current meeting to this room
                rooms_availability[room_index].append((meeting_start, meeting_end))
                rooms_usage_count[room_index] += 1
                room_found = True
                break

    most_used_room_index = 0
    for room_index in range(1, number_of_rooms):

        #Determine the index of the room used the most
        if rooms_usage_count[room_index] > rooms_usage_count[most_used_room_index]:
            most_used_room_index = room_index

    return most_used_room_index

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(m * n) – The outer loop iterates through each of the 'm' meetings. The inner loop iterates through each of the 'n' rooms to find an available one. Inside the inner loop, checking for availability takes constant time. Thus, for each meeting, we potentially iterate through all rooms. Therefore the time complexity is O(m * n).

Space Complexity

O(n) – The brute force approach, as described, requires us to keep track of how many times each room is used. This can be done using an array or a hash map of size 'n', where 'n' is the number of rooms. Additionally, we might need a temporary data structure to represent room availability which will also have size proportional to n. Therefore, the auxiliary space used is proportional to the number of rooms, n, resulting in a space complexity of O(n).

Optimal Solution

Approach

This problem is about figuring out the best way to schedule meetings in different rooms to minimize conflicts. The smart approach is to keep track of which rooms are free at what times and assign meetings accordingly, favoring rooms that have been empty for longer when possible.

Here's how the algorithm would work step-by-step:

Imagine each room has a timeline showing when it's free and when it's booked.
As you consider each meeting, look at the room timelines to see which rooms are available during the meeting's timeframe.
If multiple rooms are available, choose the room that has been free the longest, as this helps prevent any particular room from becoming a bottleneck.
If all rooms are occupied at a certain time, find the next available slot in a room and assign the meeting there, increasing the room's usage count.
Keep track of how many meetings each room has hosted, and update the timeline after each meeting is scheduled.
The room with the most hosted meetings represents the peak usage.

Code Implementation

def meeting_rooms_iii(number_of_rooms, meetings):
    room_usage_count = [0] * number_of_rooms
    room_availability = [[] for _ in range(number_of_rooms)]

    for room_index in range(number_of_rooms):
        room_availability[room_index].append([0, float('inf')])

    for start_time, end_time in meetings:
        available_rooms = []
        for room_index in range(number_of_rooms):
            for interval_start, interval_end in room_availability[room_index]:
                if start_time >= interval_start and end_time <= interval_end:
                    available_rooms.append((room_index, interval_start))
                    break

        if available_rooms:
            # Sort by the time the room has been available.
            available_rooms.sort(key=lambda x: x[1])
            chosen_room = available_rooms[0][0]
            room_usage_count[chosen_room] += 1

            for interval_index in range(len(room_availability[chosen_room])):
                interval_start, interval_end = room_availability[chosen_room][interval_index]
                if start_time >= interval_start and end_time <= interval_end:
                    # Splitting the interval into two.
                    if start_time == interval_start and end_time == interval_end:
                        del room_availability[chosen_room][interval_index]
                    elif start_time == interval_start:
                        room_availability[chosen_room][interval_index][0] = end_time
                    elif end_time == interval_end:
                        room_availability[chosen_room][interval_index][1] = start_time
                    else:
                        room_availability[chosen_room].insert(interval_index + 1, [end_time, interval_end])
                        room_availability[chosen_room][interval_index][1] = start_time
                    break
        else:
            # Find the room that becomes available soonest.
            next_available_times = []
            for room_index in range(number_of_rooms):
                earliest_end = float('inf')
                for interval_start, interval_end in room_availability[room_index]:
                    if interval_end > start_time:
                        earliest_end = min(earliest_end, interval_start)
                next_available_times.append((room_index, earliest_end))
            next_available_times.sort(key=lambda x: x[1])
            chosen_room = next_available_times[0][0]

            # Need to update availability to account for new slot
            room_usage_count[chosen_room] += 1

            earliest_end = float('inf')
            for interval_start, interval_end in room_availability[chosen_room]:
                if interval_end > start_time:
                    earliest_end = min(earliest_end, interval_start)

            # Handle cases where room needs to be split or extended
            found_interval = False
            for interval_index in range(len(room_availability[chosen_room])):
                interval_start, interval_end = room_availability[chosen_room][interval_index]
                if interval_start == earliest_end:
                    room_availability[chosen_room].insert(interval_index, [interval_start, end_time])
                    found_interval = True
                    break

            if not found_interval:
                # No suitable gap found, so append to the end
                room_availability[chosen_room].append([start_time, end_time])

            room_availability[chosen_room].sort()

            #Removing the overlaps if any
            updated_availability = []
            for interval_start, interval_end in room_availability[chosen_room]:
                if updated_availability and interval_start <= updated_availability[-1][1]:
                    updated_availability[-1][1] = max(updated_availability[-1][1], interval_end)
                else:
                    updated_availability.append([interval_start, interval_end])
            room_availability[chosen_room] = updated_availability

    max_usage = max(room_usage_count)
    for room_index in range(number_of_rooms):
        if room_usage_count[room_index] == max_usage:
            # The room with max usage is returned
            return room_index

    return -1 # No room was used

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^2 log n) – Let n be the number of meetings. For each meeting, we iterate through all rooms (up to n). Finding the earliest available room involves sorting or searching through available time slots in each room which can take O(log n) using data structures like priority queues or trees. This process is repeated for each of the 'n' meetings. Therefore, the time complexity becomes O(n * n * log n), which simplifies to O(n^2 log n).

Space Complexity

O(n) – The provided description mentions keeping track of room timelines (indicating availability) and the number of meetings hosted by each room. Assuming we have 'n' rooms, we would need a data structure (like a list or array) of size 'n' to store the number of meetings for each room. Furthermore, the timelines for each room would require space that is dependent on how time is discretized, which in the worst case is also dependent on the number of meeting intervals (and therefore dependent on n). Thus, the space complexity is primarily influenced by the need to store information about each room, resulting in an auxiliary space of O(n).

Edge Cases

Case	How to Handle
meetings is null or empty	Return 0 since no meetings occurred and room 0 is the default.
n (number of rooms) is 1 and there are meetings	Assign all meetings to the only available room (room 0).
meetings array contains overlapping meeting times	The algorithm should correctly assign rooms even with overlapping meetings.
meetings array is sorted by start time, reverse sorted, or randomly sorted	The algorithm must work correctly regardless of the order of meetings in the input.
Meetings array contains meetings that start and end at the same time (duration 0)	Treat these meetings as valid events that momentarily occupy a room.
Integer overflow potential in the meeting times (start or end)	Use long data types for time representation to avoid overflow problems.
Multiple rooms have the same maximum number of meetings	Return the smallest room number among those with the maximum count.
Meetings have very large start and end times causing performance issues if directly comparing times	Consider using a priority queue or similar data structure to efficiently track available rooms based on their end times.