We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Meeting Rooms III

Number: 2479

Difficulty: Hard

Paid? No

Companies: Google, TikTok, Uber, Pinterest, Amazon, PayPal, Microsoft

Problem Description

You are given n meeting rooms numbered from 0 to n-1 and an array of meetings, where each meeting is represented as [start, end) with unique start times. Meetings are assigned as follows:

  1. Each meeting uses the unused room with the lowest number.
  2. If no room is available, the meeting is delayed until any room becomes free. The meeting retains its original duration.
  3. When multiple meetings are waiting, the one with the earlier original start time gets the room as soon as it is available. Return the room number that held the most meetings (if there are ties, return the lowest numbered room).

Key Insights

  • Use a min-heap to track currently available rooms by room number.
  • Use another min-heap to manage ongoing meetings, keyed by their finish times.
  • Process the meetings in order of their start times since they are unique.
  • When no room is available at the meeting’s start time, delay the meeting to the earliest finish time available and update its finish time by adding its original duration.
  • Count how many meetings are allocated per room and return the one with the maximum count (resolving ties by room number).

Space and Time Complexity

Time Complexity: O(m log n) where m is the number of meetings, since each meeting may require heap operations on a heap of size at most n. Space Complexity: O(m + n) due to storing meetings for sorting and maintaining the heaps (the busy heap is O(n) and the sort uses O(m)).

Solution

We simulate the meeting room allocation with two heaps:

  1. Heap for available rooms (storing just the room numbers so that the smallest numbered available room is taken first).
  2. Heap for ongoing meetings (storing pairs of [end_time, room_number]). For each meeting (processed in order by start time):
  • Free any rooms that have finished their meetings by comparing the meeting’s start time with the top of the ongoing meetings heap.
  • If there is an available room, assign the meeting immediately.
  • Otherwise, delay the meeting until the earliest room is free, update the meeting’s start and finish times accordingly.
  • Update the count for each room’s usage.
  • Finally, select the room with the maximum meeting count (choosing the smallest room number in case of ties).

Code Solutions

import heapq

def mostBooked(n, meetings):
    # Sort meetings by their original start times.
    meetings.sort(key=lambda x: x[0])
    
    # Initialize available rooms heap and ongoing meetings heap.
    available_rooms = list(range(n))
    heapq.heapify(available_rooms)
    busy_rooms = []  # Each element is (end_time, room)
    
    # Count of meetings held in each room.
    meeting_count = [0] * n
    
    for start, end in meetings:
        # Free up all rooms that have finished before the current meeting start.
        while busy_rooms and busy_rooms[0][0] <= start:
            end_time, room = heapq.heappop(busy_rooms)
            heapq.heappush(available_rooms, room)
        
        duration = end - start
        
        if available_rooms:
            # If a room is available, assign the meeting immediately.
            room = heapq.heappop(available_rooms)
            meeting_start = start
            meeting_end = start + duration
        else:
            # Delay the meeting: get the room that will be free the earliest.
            earliest_end, room = heapq.heappop(busy_rooms)
            meeting_start = earliest_end
            meeting_end = earliest_end + duration
        
        # Update the room meeting count and busy heap.
        meeting_count[room] += 1
        heapq.heappush(busy_rooms, (meeting_end, room))
    
    # Return the room with the maximum meeting count (lowest numbered in case of tie).
    return meeting_count.index(max(meeting_count))

# Example usage:
print(mostBooked(2, [[0,10],[1,5],[2,7],[3,4]]))  # Expected output: 0
← Back to All Questions