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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Meeting Rooms III

Difficulty: Hard

Problem Description

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). Meetings are allocated to rooms based on availability, and if all rooms are occupied, meetings will be delayed. The goal is to return the number of the room that held the most meetings, with the lowest room number being returned in case of a tie.

Key Insights

  • Meetings are scheduled in a half-closed interval format.
  • Each meeting takes place in the lowest-numbered available room.
  • If no rooms are free, the meeting is delayed but retains its original duration.
  • Prioritize earlier-starting meetings when rooms become available.
  • Maintain a count of meetings held in each room to identify the room with the most meetings.

Space and Time Complexity

Time Complexity: O(m log m + n), where m is the number of meetings (due to sorting and managing the heap). Space Complexity: O(n), for storing room availability and meeting counts.

Solution

To solve this problem, we utilize a min-heap (priority queue) to manage the availability of rooms based on the end times of meetings. We also maintain a count of meetings held in each room. The algorithm proceeds as follows:

  1. Sort the meetings by their start times.
  2. Use a min-heap to track the end times of meetings in each room.
  3. For each meeting, check if there is a free room. If a room is free, start the meeting there; if not, delay the meeting until a room is available.
  4. Update the meeting count for the room used.
  5. After processing all meetings, determine which room held the most meetings, returning the lowest-numbered room in case of a tie.

Code Solutions

import heapq

def most_meetings(n, meetings):
    meetings.sort()  # Sort meetings by start time
    room_end_times = []  # Min-heap to track end times of rooms
    room_meeting_count = [0] * n  # Count meetings held in each room

    for start, end in meetings:
        # Release rooms that have finished their meetings
        while room_end_times and room_end_times[0][0] <= start:
            heapq.heappop(room_end_times)
        
        # Check for the lowest-numbered available room
        if len(room_end_times) < n:
            room_id = len(room_end_times)  # Available room
            room_meeting_count[room_id] += 1
            heapq.heappush(room_end_times, (end, room_id))
        else:
            # Delay the meeting to when the earliest room is available
            earliest_end_time, room_id = heapq.heappop(room_end_times)
            room_meeting_count[room_id] += 1
            delayed_start = earliest_end_time
            delayed_end = delayed_start + (end - start)
            heapq.heappush(room_end_times, (delayed_end, room_id))
    
    # Find the room with the most meetings
    max_meetings = max(room_meeting_count)
    return room_meeting_count.index(max_meetings)
← Back to All Questions