Minimize the Maximum Difference of Pairs

lcpy gen -n 2616   # by problem number
lcpy gen -s minimize_the_maximum_difference_of_pairs   # by problem name

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:
    # Time: O(n log n + n log m) where m = max(nums) - min(nums)
    # Space: O(n) for the sorted copy
    def minimize_max(self, nums: list[int], p: int) -> int:
        vals = sorted(nums)
        n = len(vals)

        def can_pair(target: int) -> bool:
            count = 0
            i = 0
            while i < n - 1:
                if vals[i + 1] - vals[i] <= target:
                    count += 1
                    i += 2
                else:
                    i += 1
            return count >= p

        low, high = 0, vals[-1] - vals[0]
        while low < high:
            mid = (low + high) // 2
            if can_pair(mid):
                high = mid
            else:
                low = mid + 1
        return low