Minimize Maximum Difference
Given N integers, you want to partition them into N/2 pairs. The difference of a pair (a, b) is |a - b|. Your goal is to minimize the maximum difference among all pairs. Print this minimum possible maximum difference.
Input
The first line contains an integer N (2 <= N <= 200000), which is an even number. The second line contains N distinct integers a_1, a_2, ..., a_N (-10^9 <= a_i <= 10^9).
Output
Print a single integer: the minimum possible maximum difference between any pair.
Constraints
N is an even integer, 2 <= N <= 200000. All a_i are distinct. -10^9 <= a_i <= 10^9.
Example 1
4 1 2 3 4
1
Pairs (1,2) and (3,4) give max diff 1. Pairs (1,3) and (2,4) give max diff 2. Pairs (1,4) and (2,3) give max diff 3. Minimum max diff is 1.
Example 2
6 10 50 20 60 30 40
10
Sorted array: [10, 20, 30, 40, 50, 60]. Pairs (10,20), (30,40), (50,60) give max diff 10. Minimum max diff is 10.
Hints
Similar problems
- Minimum Maximum DifferenceMedium
- Maximum Non-overlapping IntervalsMedium
- Minimize Maximum Difference in PairsMedium
- Minimum Maximum Height DifferenceMedium
- Minimize Maximum Segment SumMedium
- Maximize Minimum DifferenceMedium
More topics: Sorting problems, Binary Search problems, Greedy problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 1 2 3 4
6 10 50 20 60 30 40