0960MediumArrayTwo PointersSorting

Earliest Window Both Are Free

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Two people's free periods are given as slots1 and slots2, each entry a pair [start, end] meaning free from start up to end. A person's own periods never overlap each other.

Find the earliest moment t at which both are free for a stretch of duration, that is where the whole of t to t + duration lies inside one period of each.

Return [t, t + duration], or an empty list when no such moment exists.

Examples

Example 1

Input: slots1 = [[14, 27], [40, 55], [70, 90]], slots2 = [[20, 33], [50, 60], [80, 95]], duration = 8
Output: [80, 88]

The first overlap runs from 20 to 27, only seven long. The next runs from 50 to 55, five long. The one from 80 to 90 is ten long, so the stretch starts at 80.

Example 2

Input: slots1 = [[0, 5]], slots2 = [[5, 10]], duration = 1
Output: []

The two periods meet at a single moment and overlap over nothing, so there is no room even for a stretch of one.

Example 3

Input: slots1 = [[10, 20], [0, 5]], slots2 = [[0, 30]], duration = 5
Output: [0, 5]

The periods are not given in order, and sorting them first shows the earliest workable overlap starts at 0.

Constraints

1 <= slots1.length <= 10^4
1 <= slots2.length <= 10^4
slots1[i].length == 2
slots2[i].length == 2
slots1[i][0] < slots1[i][1]
slots2[i][0] < slots2[i][1]
0 <= slots1[i][j] <= 10^9
0 <= slots2[i][j] <= 10^9
1 <= duration <= 10^6
Neither person's own periods overlap each other

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_available_duration(slots1: list[list[int]], slots2: list[list[int]], duration: int) -> list[int]:

Java

public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration)

The intended approach

Time O(a log a + b log b) for periods numbered a and b, the sorting dominating.Space O(a + b) for the sorted lists.

A stretch works only where the two people's periods overlap, so the task is to find the earliest overlap long enough to hold it. Sort both lists by start, then walk them with a pointer each. The overlap of the two periods under the pointers runs from the later of their starts to the earlier of their ends, and if that is at least `duration` long the answer starts at the later start, since walking in order means no earlier overlap was missed. Otherwise the period that ends first can never help again, because every later period on the other side starts no earlier, so move that pointer on. Each step retires one period, which is what keeps the walk linear after the sorting.

Pythonentry point: min_available_duration

def min_available_duration(slots1, slots2, duration):
    first = sorted(slots1)
    second = sorted(slots2)
    i = 0
    j = 0
    while i < len(first) and j < len(second):
        start = first[i][0] if first[i][0] > second[j][0] else second[j][0]
        end = first[i][1] if first[i][1] < second[j][1] else second[j][1]
        if end - start >= duration:
            return [start, start + duration]
        if first[i][1] < second[j][1]:
            i += 1
        else:
            j += 1
    return []

The obvious version

Take every pairing of one person's period with the other's, work out where they overlap, and keep the earliest overlap long enough to hold the stretch. Quadratic in the period counts and it never sorts or retires anything.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_available_duration(slots1, slots2, duration):
    best = None
    for a in slots1:
        for b in slots2:
            start = a[0] if a[0] > b[0] else b[0]
            end = a[1] if a[1] < b[1] else b[1]
            if end - start >= duration:
                if best is None or start < best:
                    best = start
    if best is None:
        return []
    return [best, best + duration]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in