LeetCode 1229 - Meeting Scheduler

This problem asks us to find the earliest overlapping time slot of a given duration between two people, given their individual availability schedules.

leetcodemediumarraytwo-pointerssorting

LeetCode Problem 1229

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Sorting

Solution

Problem Understanding

This problem asks us to find the earliest overlapping time slot of a given duration between two people, given their individual availability schedules. Each person's availability is represented as an array of non-overlapping time slots [start, end], where start and end are integers indicating the inclusive time range. The meeting duration is a single integer duration. The expected output is the earliest time slot [start, start + duration] that fits within both people's availability, or an empty array if no such slot exists.

The constraints tell us that each person can have up to 10,000 time slots, and the start and end times can be as large as 10^9. This implies that a naive solution checking every combination of slots from both people would be too slow (up to 10^8 comparisons). Importantly, no two slots for the same person overlap, so each person's schedule is already internally consistent. The duration is guaranteed to be at least 1 and no more than 10^6, which ensures that it can be meaningfully compared against the slot lengths.

Edge cases to consider include when the first slot of one person is entirely after the last slot of the other person, when a slot is shorter than the required duration, and when slots touch exactly at their endpoints but do not overlap sufficiently for the meeting duration.

Approaches

A brute-force approach would iterate over every pair of time slots from slots1 and slots2. For each pair, it would calculate the intersection and check if it can accommodate the duration. This works because it examines all possibilities, but it is computationally expensive. If each person has 10,000 slots, this approach could require up to 100 million comparisons, which is too slow for the given input size.

The key insight for an optimal solution is that by sorting the slots by start time and using a two-pointer technique, we can efficiently find overlapping slots without checking every pair. After sorting, we start with the first slot of each person and calculate their intersection. If the intersection is long enough, we return it immediately. Otherwise, we advance the pointer for the slot that ends earlier, because any overlap with the current slot of the other person is impossible beyond that end.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Check every pair of slots for overlap
Optimal O(n log n + m log m) O(1) Sort both arrays and use two pointers to find the earliest intersection

Algorithm Walkthrough

  1. Sort both schedules: Sort slots1 and slots2 by their start times. This ensures we always consider the earliest available slots first, which guarantees that the first valid intersection we find is the earliest possible.
  2. Initialize two pointers: Set i = 0 for slots1 and j = 0 for slots2.
  3. Iterate through both lists: While i < len(slots1) and j < len(slots2), do the following steps:
  4. Compute the overlap: For the current slots slot1 = slots1[i] and slot2 = slots2[j], compute start_overlap = max(slot1[0], slot2[0]) and end_overlap = min(slot1[1], slot2[1]). This gives the range where both people are available.
  5. Check duration requirement: If end_overlap - start_overlap >= duration, return [start_overlap, start_overlap + duration]. This is the earliest slot satisfying the duration.
  6. Advance the pointer: Move the pointer of the slot that ends first (if slot1[1] < slot2[1] then i += 1 else j += 1). The intuition is that the shorter slot cannot overlap further with the other person's later slots.
  7. No slot found: If the loop ends without returning, return an empty array [].

Why it works: Sorting ensures that we always examine slots in chronological order. The two-pointer method guarantees that we never miss an overlap that could satisfy the duration because we always progress past slots that cannot contribute to future intersections. The invariant maintained is that slots1[i] and slots2[j] are the earliest remaining candidate slots that could overlap.

Python Solution

from typing import List

class Solution:
    def minAvailableDuration(self, slots1: List[List[int]], slots2: List[List[int]], duration: int) -> List[int]:
        # Sort both people's slots by start time
        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):
            start_overlap = max(slots1[i][0], slots2[j][0])
            end_overlap = min(slots1[i][1], slots2[j][1])
            
            if end_overlap - start_overlap >= duration:
                return [start_overlap, start_overlap + duration]
            
            # Advance the pointer of the slot that ends first
            if slots1[i][1] < slots2[j][1]:
                i += 1
            else:
                j += 1
                
        return []

The implementation begins by sorting both schedules so that we can efficiently scan in chronological order. It then iterates through both lists, computing overlaps and checking the duration. Advancing the pointer for the slot that ends first ensures we do not miss any potential intersections while avoiding unnecessary comparisons.

Go Solution

import "sort"

func minAvailableDuration(slots1 [][]int, slots2 [][]int, duration int) []int {
    sort.Slice(slots1, func(i, j int) bool { return slots1[i][0] < slots1[j][0] })
    sort.Slice(slots2, func(i, j int) bool { return slots2[i][0] < slots2[j][0] })

    i, j := 0, 0
    for i < len(slots1) && j < len(slots2) {
        startOverlap := max(slots1[i][0], slots2[j][0])
        endOverlap := min(slots1[i][1], slots2[j][1])

        if endOverlap-startOverlap >= duration {
            return []int{startOverlap, startOverlap + duration}
        }

        if slots1[i][1] < slots2[j][1] {
            i++
        } else {
            j++
        }
    }

    return []int{}
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

In Go, we use sort.Slice to sort the two schedules and define helper functions max and min for readability. The logic mirrors the Python solution exactly. Empty slices []int{} are returned when no meeting slot is found.

Worked Examples

Example 1: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8

i j slots1[i] slots2[j] start_overlap end_overlap Result/Advance
0 0 [10,50] [0,15] 10 15 15-10 = 5 < 8 → advance j
0 1 [10,50] [60,70] 60 50 end_overlap < start_overlap → advance i
1 1 [60,120] [60,70] 60 70 70-60 = 10 >= 8 → return [60,68]

Example 2: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12

i j slots1[i] slots2[j] start_overlap end_overlap Result/Advance
0 0 [10,50] [0,15] 10 15 15-10 = 5 < 12 → advance j
0 1 [10,50] [60,70] 60 50 end_overlap < start_overlap → advance i
1 1 [60,120] [60,70] 60 70 70-60 = 10 < 12 → advance j
j = 2 → loop ends → return []

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + m log m) Sorting both lists dominates, iterating through slots is linear
Space O(1) No additional data structures beyond pointers; in-place sorting assumed

Sorting dominates the time complexity. Two-pointer traversal is linear, and no extra memory is needed beyond loop variables.

Test Cases

# Provided examples