0736MediumArrayBinary SearchSorting

Next Free Maintenance Window

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.

A depot logs its maintenance windows as windows, where windows[i] = [open_i, close_i] gives the offset in minutes, measured from the daily shift changeover, at which window i opens and the offset at which it closes. Offsets before the changeover are negative. Every window satisfies open_i <= close_i, and no two windows share an opening offset.

For each window i the dispatcher wants its follower: the window j whose opening offset is the smallest one that is still at least close_i. A window may be its own follower when its opening and closing offsets are equal. If no window opens at or after close_i, window i has no follower.

Return an array res of the same length as windows, where res[i] is the index of the follower of window i, or -1 when window i has no follower.

Examples

Example 1

Input: windows = [[14, 22], [-5, 3], [23, 30]]
Output: [2, 0, -1]

Window 0 closes at 22, and window 2 opens at 23, the smallest opening offset that is at least 22. Window 1 closes at 3, and window 0 opens at 14, the smallest opening offset that is at least 3. Window 2 closes at 30 and no window opens at or after 30.

Example 2

Input: windows = [[7, 7], [8, 12]]
Output: [0, -1]

Window 0 opens and closes at 7, so its own opening offset of 7 is at least its closing offset and it is its own follower. Window 1 closes at 12 and the only openings on record are 7 and 8, both below 12.

Example 3

Input: windows = [[-40, -18], [-18, 9], [55, 61]]
Output: [1, 2, -1]

Window 0 closes at -18 and window 1 opens at -18. Window 1 closes at 9 and the only opening at or after 9 is window 2's opening of 55. Window 2 closes at 61, later than every opening on record.

Constraints

1 <= windows.length <= 2 * 10^4
windows[i].length == 2
-10^6 <= windows[i][j] <= 10^6
windows[i][0] is at most windows[i][1] for every window.
No two windows have the same opening offset.

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 next_window(windows: list[list[int]]) -> list[int]:

Java

public int[] nextWindow(int[][] windows)

The intended approach

Time O(n log n) for n windows: one sort plus a binary search per window.Space O(n) for the sorted pairs and the returned array.

Build one sorted list of `(opening offset, original index)` pairs, so the openings alone form a sorted array while each opening still remembers where it came from. For a window with closing offset `c`, the follower is the leftmost entry of that sorted array whose opening is not below `c`, which a lower-bound binary search finds directly; if the search runs off the end there is no follower. Report the remembered original index, not the position inside the sorted list.

Pythonentry point: next_window

def next_window(windows):
    # sort the (opening, original index) pairs once, then binary search the
    # sorted openings for each window's closing offset.
    # O(n log n) time, O(n) space.
    order = sorted((w[0], i) for i, w in enumerate(windows))
    opens = [p[0] for p in order]
    out = []
    for w in windows:
        close = w[1]
        lo, hi = 0, len(opens)
        while lo < hi:
            mid = (lo + hi) // 2
            if opens[mid] < close:
                lo = mid + 1
            else:
                hi = mid
        out.append(-1 if lo == len(opens) else order[lo][1])
    return out

The obvious version

For each window, walk the entire list and keep the qualifying window with the smallest opening offset seen so far. Quadratic, but it uses no ordering and no search structure.

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_next_window(windows):
    """For every window, scan the whole list and keep the smallest qualifying
    opening. No sorting and no search structure."""
    out = []
    for w in windows:
        best_open = None
        best_idx = -1
        for j, other in enumerate(windows):
            if other[0] >= w[1]:
                if best_open is None or other[0] < best_open:
                    best_open = other[0]
                    best_idx = j
        out.append(best_idx)
    return out

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