1475. Sensors Only Where There Is a Socket
n zones must each hold at least one sensor. Zone i is the CLOSED stretch
[l, r] with l <= r, and a sensor at position x serves zone i exactly
when l <= x <= r, endpoints included. Sensors can only be placed at one of
m given socket positions, which may repeat and arrive in no particular order.
Print the fewest sensors, or -1 if some zone cannot be served at all.
zones [1,5] [2,6] [8,9] [3,4], sockets 0 4 7 8 10 -> 2
zones [1,3] [3,5] [5,7], sockets 3 4 5 -> 2
zones [1,3] [5,7], sockets 4 -> -1
Trace the second line. Sorting the zones by right endpoint gives [1,3],
[3,5], [5,7]. The largest socket at or below 3 is 3, so a sensor goes
there; it also serves [3,5], because the two zones merely TOUCH at 3 and
under the CLOSED reading both contain it. [5,7] is not served, and the largest socket at or below 7 is 5, so
a second sensor goes there. Two sensors. Under a HALF-OPEN reading the sensor
at 3 would not serve [3,5] and three would be needed.
## What most people try first
Placing a sensor at the socket nearest the middle of each unserved zone, or at
its first socket. On [1,10] [2,3] [4,5] [6,7] with sockets 2 4 6 8 10, a
rule that serves [1,10] first and picks 10 wastes the chance to serve
something else, and the short zones then need one each: four sensors where
three suffice.
The second reflex is to try every subset of sockets, which is 2^m.
## Sort the zones by right endpoint, take the furthest socket that still fits
sort the sockets, ascending
sort the zones by r, ascending
last = nothing yet
count = 0
for each zone [l, r] in that order:
if last exists and l <= last <= r: continue already served
x = the largest socket <= r one binary search
if x does not exist or x < l: return -1
last = x; count += 1
return count
O((n + m) log(n + m)): two sorts and one binary search per zone.
## Why one remembered sensor is enough
The zones are processed in increasing order of r, and every sensor placed so
far sits at a position at most the current r, since it was chosen as the
largest socket at or below an earlier, smaller r. So the sensors are placed
in non-decreasing position, and the LAST one placed is the rightmost. If any
sensor serves the current zone, the rightmost one does, because serving means
lying in [l, r] and a sensor further left is further from l. Checking
last alone is therefore the same as checking all of them.
## Why the greedy is optimal, by an exchange argument
Take any valid placement and the zone z with the smallest r. Some sensor
serves it, at a socket x with l_z <= x <= r_z. Let x' be the largest
socket at or below r_z; then x <= x' <= r_z, and x' >= x >= l_z, so x'
serves z too.
Move that sensor from x to x'. Any zone served at x has l <= x and
r >= x, and since r >= r_z by the choice of z, we get r >= r_z >= x'
and l <= x <= x', so it is still served. The placement stays valid and the
same size, and its first sensor is now the greedy's choice. Induction on the
remaining zones finishes it.
## The boundary that breaks a careless implementation
The socket must satisfy x >= l as well as x <= r. Finding the largest
socket at or below r and forgetting to check it against l reports a
solution for a zone that has no socket in it at all, which is the third sample.
And the "already served" test is l <= last <= r, both non-strict, because the
zones are closed.
## Overflow
Coordinates reach 10^9 in magnitude and nothing is summed, so a signed 32 bit
integer, limit 2147483647, holds every value. The count is at most n.
## Related
Problem 1094 fires arrows at balloons from ANY position, so a solution always
exists and the answer is never -1; restricting the positions to a given list
is what makes the problem able to fail. Problem 1471 is the same free-position
question under the half-open reading. Problem 1095 covers given checkpoints
with given stretches, which is this problem with the roles of the points and
the intervals swapped.
Constraints - `1 ≤ n ≤ 200000` and `1 ≤ m ≤ 200000` - `-10^9 ≤ l ≤ r ≤ 10^9` - `-10^9 ≤ each socket position ≤ 10^9` - each zone is the closed stretch `[l, r]`, so a sensor on either endpoint serves it - socket positions may repeat and arrive in no particular order
Input
The first line contains two integers n and m.
Each of the next n lines contains two integers l and r, one zone, in no particular order.
The last line contains m integers, the socket positions, in no particular order and possibly with repeats.
Output
Print one integer alone on its own line: the fewest sensors, each placed at one of the given socket positions, such that every zone contains at least one sensor. Print -1 if some zone contains no socket at all. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.