2616 - Minimize the Maximum Difference of Pairs (Medium)

Input: nums = [10,1,2,7,1,3], p = 2
Output: 1
Explanation: The first pair is formed from the indices 1 and 4, and the second pair is formed from the indices 2 and 5.
The maximum difference is max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Therefore, we return 1.

Input: nums = [4,2,1,2], p = 1
Output: 0
Explanation: Let the indices 1 and 3 form a pair. The difference of that pair is |2 - 2| = 0, which is the minimum we can attain.

class Solution {
public:
    // min max -> think of binary search
    int minimizeMax(vector<int>& nums, int p) {
        // sort the input first
        sort(nums.begin(), nums.end());
        // the possible difference ranges from 0 to the largest value - the smallest value
        int n = nums.size(), l = 0 , r = nums.back() - nums.front();
        // binary search the min max diff
        while (l < r) {
            int m = l + (r - l) / 2, cnt = 0;
            for (int i = 1; i < n; i++) {
                // we can make a pair
                if (nums[i] - nums[i - 1] <= m) {
                    // increase the number of pairs
                    cnt += 1;
                    // increase i by 1
                    // since it is included in the pair already
                    i += 1;
                }
            }
            // not enough pairs, move l pointer excluding m
            if (cnt < p) l = m + 1;
            // too many pairs, move r to m
            else r = m;
        }
        return l;
    }
};