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 II

Number: 253

Difficulty: Medium

Paid? Yes

Companies: Amazon, Meta, Google, Bloomberg, Microsoft, TikTok, Oracle, Netflix, Uber, Hubspot, Apple, Cisco, Two Sigma, Salesforce, Splunk, Capital One, IBM, Snap, Goldman Sachs, Yandex, PayPal, Lyft, eBay, Pinterest, ServiceNow, Miro, PubMatic, Nordstrom, SoFi

Problem Description

Given an array of meeting time intervals where each interval is represented as [start, end], determine the minimum number of conference rooms required so that all meetings can take place without overlapping.

Key Insights

  • Sort the intervals based on start times to process meetings in order.
  • Use a min-heap (priority queue) to keep track of meeting end times.
  • When processing a new meeting, check if its start time is greater than or equal to the smallest end time from the heap.
  • If so, it means a meeting room has been freed (the meeting with the smallest end time has ended) and can be reused.
  • If not, allocate a new room by pushing the current meeting's end time into the heap.
  • The size of the heap at any moment represents the number of rooms currently in use.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and each heap operation (push/pop) taking O(log n).
Space Complexity: O(n) in the worst-case scenario when all meetings overlap, requiring all end times in the heap.

Solution

The solution involves first sorting the meeting intervals by their start times. Then, we utilize a min-heap (priority queue) to keep track of the end times of ongoing meetings. For each meeting, we compare its start time with the smallest end time in the heap:

  • If the meeting can start after the meeting at the top of the heap has ended (i.e., its start time is greater than or equal to the smallest end), we remove that end time from the heap (freeing up a room).
  • Then, we add the current meeting's end time to the heap. By the end of processing all meetings, the size of the heap represents the minimum number of conference rooms required.

Code Solutions

import heapq

def minMeetingRooms(intervals):
    # Sort intervals based on start time
    intervals.sort(key=lambda x: x[0])
    
    # Initialize a min-heap to store end times of meetings that are currently using rooms
    min_heap = []
    
    # Process each meeting interval
    for interval in intervals:
        start, end = interval
        
        # If the heap is not empty and the current meeting starts after the earliest ended meeting
        if min_heap and start >= min_heap[0]:
            heapq.heappop(min_heap)  # Reuse the room
        
        # Allocate the current meeting end time into the heap (new or reused room)
        heapq.heappush(min_heap, end)
    
    # The number of rooms is the number of simultaneous meetings
    return len(min_heap)

# Example usage:
intervals = [[0,30],[5,10],[15,20]]
print(minMeetingRooms(intervals))  # Output: 2
← Back to All Questions