934. The Shortest Interval Covering Each Query
You are given n intervals, each a pair l r meaning every integer from l
to r inclusive. Then q queries arrive, each a single point x.
For each query print the LENGTH of the shortest interval containing x, where
the length of [l, r] is r - l + 1, or -1 if no interval contains x.
``` intervals [1,4] [2,4] [3,6] [4,4], queries 2, 3, 4, 5 -> 3 / 3 / 1 / 4
intervals [1,1], queries 1, 2 -> 1 / -1 ```
## What most people try first
Checking every interval for every query is O(nq). At n = q = 10^5 that is
10^10.
Sorting the intervals by length and, for each query, scanning from the shortest until one contains the point is worse in the worst case, since a query near no short interval scans everything.
## The method: answer the queries OFFLINE, in point order
The queries do not have to be answered in the order they are given. Sort them by their point, remember where each came from, and sweep.
sort intervals by left end
sort the query indices by their point
h = min-heap of (length, right end)
i = 0
for each query point x, in increasing order:
while i < n and l[i] <= x: push (length, r) for interval i; i = i + 1
while h is not empty and the top's right end < x: pop it
answer = the top's length if the heap is non-empty, else -1
print the answers back in the ORIGINAL query order
The heap is keyed by LENGTH, so its top is the shortest candidate. Each entry also carries its own right end, which is how it is recognised as expired.
## Why lazy deletion is the right call here
At the moment the sweep reaches x, the heap holds every interval with
l <= x. Some of those have r < x and no longer contain the point. Removing
one at the moment it expires would mean finding it inside a heap ordered by
LENGTH, where nothing is arranged by right end, so the search is linear.
Instead they stay put and are discarded from the top when they surface. That is
safe, and here is the argument: an interval discarded at point x has r < x,
and the sweep only ever moves right, so it can never contain any later query
point either. Nothing that is thrown away could have been needed again.
Each interval is pushed once and popped at most once over the whole run, so the
discarding costs O(n log n) in total, not per query.
## Why the top is the answer
After the discard loop, every entry in the heap has l <= x and r >= x, so
every one of them contains x. The heap is ordered by length, so the top is
the shortest of them. And every interval containing x has l <= x, so it was
pushed before the query was answered, and r >= x, so it was not discarded.
The heap therefore holds exactly the intervals containing x, and its top is
the answer.
## The boundary that breaks a careless implementation
The push test is l <= x, and the discard test is r < x. Both boundaries are
inclusive on the interval, so an interval [4,4] answers a query at 4 with
length 1, which the first example checks.
The answers must be reordered before printing. Sorting the queries and printing in sorted order is the mistake that this shape invites, and it produces a plausible-looking wrong answer whenever the queries are not already sorted.
The interval pointer never resets. Once pushed, an interval stays in the heap until it expires.
## Overflow
Ends reach 10^9, so a length reaches 10^9 too, and both fit in a signed
32-bit integer, which holds 2147483647. Nothing is summed. The one expression
to check is r - l + 1 with l = 1 and r = 10^9, which is 10^9, still
inside. There is no overflow in this problem.
## Related problems
Problem #914 sweeps events with a heap and lazy deletion where the staleness test is a right edge carried in the entry, exactly as here, and problem #930 does the same with a rot day. What is new here is that the QUERIES are reordered: the sweep is driven by the questions rather than by the data, and the answers have to be put back. That offline reordering is the technique to take away, and problem #829 applies it to a different family of queries.
## Cost
Time O((n + q) log n). Space O(n + q).
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ q ≤ 100000` - `1 ≤ l ≤ r ≤ 10^9` - `1 ≤ x ≤ 10^9`
Input
The first line contains an integer n.
Each of the next n lines contains two integers: the left and right ends of one interval.
The next line contains an integer q.
The following line contains q query points.
Output
Print one line per query, in the ORDER THE QUERIES WERE GIVEN: the length of the shortest interval containing that point, or -1 if none contains it.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.