Meeting Scheduler - Leetcode Solution

Problem Statement: Given the schedules of two persons as lists of intervals, you need to find the available slots for them to meet for a specified duration. You need to output all such slots that are common to both persons and of sufficient duration.

Example 1: Person 1: [[9, 10], [12, 14], [15, 16]] Person 2: [[11, 12], [13, 14], [16, 17]] Duration: 1 Output: [[11, 12], [13, 14]]

Example 2: Person 1: [[10, 12], [13, 14], [17, 19]] Person 2: [[7, 9], [11, 13], [16, 18]] Duration: 2 Output: [[13, 14]]

Approach: We need to find the available slots for both persons and then compare them to find the common intervals. To find the available slots of each person, we first need to merge any overlapping intervals. Then, we can find the gaps between the merged intervals that are greater than or equal to the specified duration. Finally, we can compare the available slots of both persons to find the common intervals.

Algorithm:

1. Merge overlapping intervals of both persons.
2. For each person, find the gaps between the merged intervals that are greater than or equal to the specified duration.
3. Compare the available slots of both persons to find the common intervals.
4. Return the common intervals.

Code:

class Solution: def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:

    # Merge overlapping intervals of both persons
    merged_slots = sorted(slots1 + slots2)

    i = 0
    j = 1
    
    while j < len(merged_slots):
        
        if merged_slots[j][0] <= merged_slots[i][1]:
            merged_slots[i][1] = max(merged_slots[i][1], merged_slots[j][1])
            j += 1
        else:
            i += 1
            merged_slots[i] = merged_slots[j]
            j += 1
            
    # Find gaps between merged intervals that are >= duration
    available_slots1 = []
    available_slots2 = []
    
    for i in range(len(merged_slots) - 1):
        if merged_slots[i + 1][0] - merged_slots[i][1] >= duration:
            if merged_slots[i][0] in [slot[0] for slot in slots1]:
                available_slots1.append([merged_slots[i][0], merged_slots[i][1]])
                
            if merged_slots[i][0] in [slot[0] for slot in slots2]:
                available_slots2.append([merged_slots[i][0], merged_slots[i][1]])
    
    # Find common slots
    common_slots = []
    
    for slot1 in available_slots1:
        for slot2 in available_slots2:
            if max(slot1[0], slot2[0]) + duration <= min(slot1[1], slot2[1]):
                common_slots.append([max(slot1[0], slot2[0]), max(slot1[0], slot2[0]) + duration])
                
    return common_slots

Time Complexity: The time complexity of the solution is O(n log n), where n is the total number of intervals as we need to sort the intervals. The space complexity of the solution is O(n) to store the merged intervals.

1