Show problems as
Classic problem #436MediumArrayBinary SearchSorting

Find Right Interval

Real-world version: Next Free Maintenance Window
Tracked in this browser only
Read Find Right Interval on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def next_window(windows: list[list[int]]) -> list[int]:
Java
public int[] nextWindow(int[][] windows)

More on the same topics