Meeting Scheduler

December 26, 2023

Problem #

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration, return the earliest time slot that works for both of them and is of duration.

Solution #

To solve this problem, we need to find a common time slot between two schedules (slots1 and slots2) that is at least as long as the given meeting duration. A practical approach is to sort both schedules based on start times and then iterate through them to find overlapping intervals that can accommodate the meeting duration.

Here’s the Python code to achieve this:

def minAvailableDuration(slots1, slots2, duration):
    
    slots1.sort(key=lambda x: x[0])
    slots2.sort(key=lambda x: x[0])

    i, j = 0, 0

    while i < len(slots1) and j < len(slots2):
        # Find the overlap between the two slots
        start = max(slots1[i][0], slots2[j][0])
        end = min(slots1[i][1], slots2[j][1])

        # Check if the overlap can accommodate the duration
        if end - start >= duration:
            return [start, start + duration]

        # Move to the next slot in the array that ends earlier
        if slots1[i][1] < slots2[j][1]:
            # Person 1's slot ends before person 2's, advance person 1
            i += 1
        else:
            # Person 2's slot ends before person 1's, advance person 2
            j += 1

    return []

# Example Usage
slots1 = [[10, 50], [60, 120], [140, 210]]
slots2 = [[0, 15], [60, 70]]
duration = 8
print("Earliest time slot:", minAvailableDuration(slots1, slots2, duration))

In this code:

• Both slots1 and slots2 are first sorted based on the start time of each slot.
• We then iterate through both arrays simultaneously using two pointers, i and j.
• In each iteration, we calculate the overlap between the current slots from slots1 and slots2.
• If the overlap is greater than or equal to the desired duration, we return the earliest start time of this overlapping interval and the start time plus the duration.
• If no overlap is found, or if the overlap is not long enough, we move to the next slot in the array that has the earlier ending time.
• If we finish iterating through either of the arrays without finding a suitable interval, we return an empty list, indicating no common time slot was found.

This algorithm ensures we check all possible overlaps in a time-efficient manner, with a time complexity of O(N log N + M log M), where N and M are the lengths of slots1 and slots2, respectively. The sorting dominates the time complexity.