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 Scheduler

Number: 1165

Difficulty: Medium

Paid? Yes

Companies: Datadog, Google, Uber, Citadel, Amazon, PayPal

Problem Description

Given two arrays slots1 and slots2 where each element represents an available time slot in the form [start, end] for two people, determine the earliest time slot which is common to both and whose duration is at least the specified duration. If no such time slot exists, return an empty array.

Key Insights

  • Sort both time slot arrays by their start times to simplify the overlap checking process.
  • Use a two-pointer approach to traverse the sorted arrays concurrently.
  • For each pair of slots examined, compute the intersection by taking the maximum of the start times and the minimum of the end times.
  • Check if this overlapping duration is at least as long as the required meeting duration; if so, return the earliest valid meeting interval.
  • Advance the pointer corresponding to the slot that ends earlier to look for a potentially better overlapping slot further on.

Space and Time Complexity

Time Complexity: O(n log n + m log m), where n and m are the number of slots in slots1 and slots2, respectively, due to sorting. The merging process itself runs in O(n + m). Space Complexity: O(1) additional space (ignoring the space used for sorting if done in-place).

Solution

The solution involves first sorting both slots1 and slots2 by their start times. Then, using a two-pointer approach, iterate over both sorted lists simultaneously. For each pair of slots, calculate the possible overlapping time interval by taking max(slot1_start, slot2_start) as the start and min(slot1_end, slot2_end) as the end. If the duration of the overlap is at least as long as the required duration, the earliest feasible meeting time is found and we return the interval starting at this overlap start and ending at (overlap start + duration). If the overlap is insufficient, advance the pointer of the slot that ends first since that slot cannot provide a sufficient overlap with any future slots from the other list.

Code Solutions

# Python solution for Meeting Scheduler

def meeting_scheduler(slots1, slots2, duration):
    # Sort both lists based on start time
    slots1.sort(key=lambda x: x[0])
    slots2.sort(key=lambda x: x[0])
    
    # Initialize two pointers for both lists
    i, j = 0, 0
    
    # Iterate through both lists until one pointer reaches the end
    while i < len(slots1) and j < len(slots2):
        # Calculate the latest start and earliest end of the two slots
        start = max(slots1[i][0], slots2[j][0])
        end = min(slots1[i][1], slots2[j][1])
        
        # Check if overlapping duration is enough for the meeting
        if end - start >= duration:
            return [start, start + duration]
            
        # Move the pointer that has the earlier end time
        if slots1[i][1] < slots2[j][1]:
            i += 1
        else:
            j += 1
            
    # If no valid meeting slot is found, return an empty list
    return []

# Example usage:
# print(meeting_scheduler([[10,50],[60,120],[140,210]], [[0,15],[60,70]], 8))
← Back to All Questions