Solution Explanation: Finding the Earliest Meeting Time

This problem requires finding the earliest time slot of a specified duration (duration) that is available for two people, given their respective availability slots (slots1 and slots2).

Approach: Sorting and Two Pointers

The optimal approach combines sorting and a two-pointer technique for efficient searching. Here's a breakdown:

1. Sorting: We begin by sorting both slots1 and slots2 based on the start time of each interval. This allows us to iterate through the slots in increasing order of availability. This step takes O(m log m + n log n) time, where 'm' and 'n' are the lengths of slots1 and slots2 respectively.

2. Two Pointers: We use two pointers, i and j, to iterate through the sorted slots1 and slots2 arrays, respectively. At each step:

   • We find the start time as the maximum of the current start times from both arrays (both people must be available).
   • We find the end time as the minimum of the current end times from both arrays (the meeting must end within both people's availability).
   • We check if end - start is greater than or equal to duration. If it is, we've found a suitable time slot and return [start, start + duration].
   • If the slot is too short, we advance the pointer corresponding to the array whose current interval ends earlier. This is because advancing the pointer with the earlier end time is the only way to find a longer common interval.

3. No Common Slot: If the pointers reach the end of either array without finding a suitable slot, it means there's no common time slot that meets the duration requirement, so we return an empty array.

Time and Space Complexity

• Time Complexity: O(m log m + n log n) due to the sorting step. The two-pointer iteration takes O(m + n) time in the worst case (iterating through both arrays completely), which is dominated by the sorting complexity.
• Space Complexity: O(log m + log n) (or O(1) depending on the implementation) due to the space used by the sorting algorithm (in-place sorting is possible). The space used by the pointers is constant.

Code Examples (with explanations embedded as comments)

The code examples below demonstrate the solution in various programming languages. The core logic remains the same across all implementations.

Python

def minAvailableDuration(slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
    slots1.sort()  # Sort slots1 by start time
    slots2.sort()  # Sort slots2 by start time
 
    i = j = 0
    while i < len(slots1) and j < len(slots2):  # Iterate until end of either array
        start = max(slots1[i][0], slots2[j][0])  # Find common start time
        end = min(slots1[i][1], slots2[j][1])  # Find common end time
 
        if end - start >= duration:  # Check if duration is met
            return [start, start + duration]  # Return the found slot
 
        if slots1[i][1] < slots2[j][1]:  # Advance the pointer to the interval ending sooner
            i += 1
        else:
            j += 1
    return []  # No suitable slot found

Java

import java.util.*;
 
class Solution {
    public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
        Arrays.sort(slots1, (a, b) -> a[0] - b[0]); // Sort slots1
        Arrays.sort(slots2, (a, b) -> a[0] - b[0]); // Sort slots2
 
        int i = 0, j = 0;
        while (i < slots1.length && j < slots2.length) { // Iterate until end of either array
            int start = Math.max(slots1[i][0], slots2[j][0]); // Find common start
            int end = Math.min(slots1[i][1], slots2[j][1]); // Find common end
 
            if (end - start >= duration) { // Check for sufficient duration
                return Arrays.asList(start, start + duration); // Return found slot
            }
 
            if (slots1[i][1] < slots2[j][1]) { // Advance pointer to sooner-ending interval
                i++;
            } else {
                j++;
            }
        }
        return new ArrayList<>(); // No suitable slot found
    }
}

The other languages (C++, Go, TypeScript, Rust) would follow a very similar structure, with the main differences being in the syntax for sorting, array handling, and function definitions. The core algorithm remains the same.