Minimize Maximum Difference in Pairs
MediumPractice library · +20 XPgreedysortingtwo pointers
You are given an array of N integers. You need to partition the N integers into N/2 pairs such that the maximum difference between any pair is minimized. Each integer must be used exactly once. If N is odd, one integer will be left out, and you should form (N-1)/2 pairs with the remaining integers.
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer: the minimum possible value for the maximum difference among all pairs.
Constraints
1 <= N <= 200000. The integers are between -10^9 and 10^9.
Time limit 2 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
4 1 1 3 6
Output
3
Sorted: [1, 1, 3, 6]. Pairs: (1,1) diff 0, (3,6) diff 3. Max diff = 3.
Example 2
Input
5 10 40 20 50 30
Output
10
Sorted: [10, 20, 30, 40, 50]. Pairs: (10,20) diff 10, (30,40) diff 10. 50 is left out. Max diff = 10.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
4 1 1 3 6
Example 2 input
5 10 40 20 50 30