768. Choosing p Closest Couples
An array of n numbers is given. You must choose exactly p pairs of indices. No index may
appear in two pairs, and some indices may be left out entirely. The COST of a pair is the
absolute difference of its two values, and the cost of the whole selection is the largest cost
among the p pairs.
Print the smallest achievable selection cost. If p is 0 the answer is 0.
a = 10 1 2 7 1 3, p = 2 answer 1 pair the two 1s, and 2 with 3
a = 4 2 1 2, p = 2 answer 2 every index is used, so both pairs are forced
a = 1 5 2 8 3 9 4, p = 3 answer 1 1 with 2, 3 with 4, 8 with 9; the 5 is skipped
a = 50 1 99 7, p = 0 answer 0 no pairs are required
## Why greedy pairing alone fails
The instinct is to sort, repeatedly take the closest remaining pair, and stop after p of them.
That is wrong, because taking the globally closest pair first can split a run. On 1 2 3 4 with
p = 2 the tightest pair is a tie, and if the tie is broken towards (2,3) then the only pair
left is (1,4) at cost 3, where the correct answer is 1.
The trouble is that a greedy on COST has to commit before knowing how many pairs it will need. Fix the cost first and the commitment disappears.
## Testing a candidate
Sort the array. Then ask: how many disjoint pairs can be formed with every cost at most m?
sort a
count = 0, i = 0
while i + 1 < n:
if a[i + 1] - a[i] <= m:
count += 1
i += 2 # both used
else:
i += 1 # a[i] cannot pair with its successor, so drop it
feasible(m) = (count >= p)
## Why only ADJACENT values need to be considered
First, in any optimal selection the two members of a pair may be assumed adjacent in the sorted
order among the chosen indices. If a pair is (x, z) with some unpaired y between them, then
replacing (x, z) by (x, y) costs no more, because y - x <= z - x. And if two pairs
interleave as x < y < z < w with pairs (x, z) and (y, w), then (x, y) and (z, w) have
costs y - x <= z - x and w - z <= w - y, so the re-pairing is no worse. Repeating these two
swaps turns any selection into one made of disjoint adjacent pairs.
Second, among adjacent-only selections the sweep above is optimal. Consider the leftmost value
a[0]. Either the sweep's choice matches some optimal selection, or it does not:
- if
a[1] - a[0] > m, thena[0]cannot be in any pair at all, since every other value is - even further away, so skipping it loses nothing;
- if
a[1] - a[0] <= m, suppose an optimal selection does not paira[0]witha[1]. Then at - most one of them is used. Swap whichever pair uses one of them so that
(a[0], a[1])is a pair - instead, discarding the other member of that pair. The count does not drop, and no cost rises.
Either way an optimal selection exists that agrees with the sweep's first decision, and the argument repeats on the rest of the array. That is why a left-to-right sweep that never reconsiders gets the maximum count.
## Why the predicate is monotone
A selection whose largest cost is at most m also has largest cost at most m + 1. So the
number of pairs achievable can only grow with m, and "at least p pairs" flips from false to
true exactly once. The answer is the FIRST true value.
## The bounds
lo = 0, achievable whenever two equal values exist, and the lowest cost any pair can have.
hi = max(a) - min(a), the largest difference in the whole array, at which every value pairs
with its neighbour and the count is n / 2 >= p.
The constraint 2p <= n guarantees feasibility at hi, which is what makes the upper bound
safe. Without it the answer might not exist and the problem would need a sentinel.
## The boundary that breaks a careless implementation
The skip branch must advance by ONE, not by two. Advancing by two on a failed match silently
discards a value that could have paired with the value after it: on 1 5 2 8 3 9 4 sorted to
1 2 3 4 5 8 9 with m = 1, stepping by two on failure loses the (8,9) pair and reports 2
instead of 3.
And p = 0 must answer 0. With lo = 0 and the count starting at 0 the plain loop already does
the right thing, but an implementation that special-cases "find the closest pair first" does
not.
## Relationship with problem 787
787 works on the same sorted array and the same pairwise differences, but ranks them: for a
threshold it counts how many pairs of positions lie within that distance, adding hi - lo at
each right end, because one value may partner with every value in its window.
Here the pairs must be DISJOINT, so a value spent on one pair is gone and the sweep steps past both members instead of accumulating a count. Same sorted order and the same threshold; what is being counted is how many close pairs can COEXIST rather than how many close pairs exist.
## Overflow
Nothing here overflows a signed 32-bit integer, and it is worth saying so rather than leaving a
warning that does not apply. Values are at most 10^9, the difference a[i + 1] - a[i] is at
most 10^9, and hi = max(a) - min(a) is at most 10^9 too, so even the careless midpoint
(lo + hi) / 2 peaks at 2 * 10^9 against an INT_MAX of 2147483647. The pair count never
passes n / 2 = 100000.
Write the midpoint as lo + (hi - lo) / 2 anyway. It costs nothing, the margin above is only
about seven percent, and it is the form that survives when the numbers grow: problem 769 runs
the same kind of search but compares PREFIX SUMS that reach 2 * 10^14, two hundred thousand
times larger than anything here, and there 64 bits are genuinely required.
## Cost
Sorting dominates: O(n log n) once, then O(n log(max - min)) for the search.
Constraints - `2 ≤ n ≤ 200000` - `0 ≤ p` and `2p ≤ n` - `0 ≤ a[i] ≤ 10^9`
Input
The first line contains two integers n and p.
The second line contains n values in any order.
Output
Print one integer on its own line: the smallest possible value of the largest pair cost. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.