2616. Minimize the Maximum Difference of Pairs

Link

Simplier version for 2790

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:

        n = len(nums)

        if n == 1:
            return 0

        c = Counter(nums)

        ll = list(c.items())
        ll.sort()

        def check(n):
            res = 0
            current = ll[0][1]

            for i in range(1, len(ll)):
                if ll[i][0] - ll[i-1][0] <= n:
                    r = min(ll[i][1], current)
                    res += r
                    current -= r
                    current += ll[i][1] - r
                else:
                    res += current // 2
                    current = ll[i][1]
                
                if res >= p:
                    return True

            return (res + current // 2) >= p

        l = 0
        r = ll[-1][0] * 2

        while l < r:
            mid = l + (r-l) // 2

            if check(mid):
                r = mid
            else:
                l = mid + 1

        return l

Faster??

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:

        n = len(nums)

        if n == 1:
            return 0

        nums.sort()

        def check(num):
            res = 0
            i = 1

            while i < n:
                if nums[i] - nums[i-1] <= num:
                    res += 1
                    i += 1
                if res >= p:
                    return True
                i += 1

            return False

        l = 0
        r = nums[-1] - nums[0]


        while l < r:
            mid = l + (r-l) // 2

            if check(mid):
                r = mid
            else:
                l = mid + 1

        return l