Tightest Coverage Window

hard

A support desk publishes on-call windows, each [start, end] (inclusive, so its size is end - start + 1). Auditors then fire timestamp queries: for each timestamp q, they want the size of the smallest window that contains it — the tightest coverage that was live at that moment — or -1 if nothing covered it.

Return a list of answers aligned with queries, in the original query order. Checking every window per query is O(n·m); the windows and queries can each number in the thousands, so aim sharper.

Example 1

in windows = [[1, 4], [2, 4], [3, 6], [4, 4]], queries = [2, 3, 4, 5]

out [3, 3, 1, 4]

q=4 fits inside [4, 4], size 1. q=5 only fits [3, 6], size 4.

Example 2

in windows = [[2, 3], [2, 5], [1, 8], [20, 25]], queries = [2, 19, 5, 22]

out [2, -1, 4, 6]

Nothing covers 19. The tightest cover of 22 is [20, 25], size 6.

Constraints

· 1 <= len(windows), len(queries) <= 2000
· 1 <= start <= end <= 10^7
· 1 <= queries[i] <= 10^7