Minimize the Maximum Difference of Pairs

Search the answer, not the pairing

Sort the numbers. Suppose a maximum allowed difference D is fixed. Scan from left to right: whenever adjacent unused values differ by at most D, take that pair and advance two positions; otherwise discard the left value and advance one. If this produces at least p disjoint pairs, D is feasible. Feasibility is monotone: any D that works continues to work when increased, so binary-search the smallest feasible value.

Why adjacent greedy is safe

When the earliest available value can pair with its next value, using that nearest partner cannot make a later pair harder than pairing it with a farther value. If it cannot pair with its next value, it cannot pair with any later sorted value under the same threshold, so skipping it is safe. That exchange argument is the important interview content. Sorting costs O(n log n); the binary search performs O(log R) scans, so total time is O(n log n + n log R) and extra space is O(1) aside from sorting. Test p=0, duplicates, and a case where a tempting nonadjacent pairing would waste a small gap.