Minimizar la Diferencia Máxima de Pares

Se te da un arreglo de enteros nums indexado desde 0 y un entero p. Encuentra p pares de índices de nums tal que la diferencia máxima entre todos los pares sea minimizada. Además, asegúrate de que ningún índice aparezca más de una vez entre los p pares.

Ten en cuenta que para un par de elementos en los índices i y j, la diferencia de este par es |nums[i] - nums[j]|, donde |x| representa el valor absoluto de x.

Devuelve la diferencia máxima mínima entre todos los p pares. Definimos el máximo de un conjunto vacío como cero.

Ejemplos

Ejemplo 1:

Input: nums = [10,1,2,7,1,3], p = 2 Output: 1 Explicación: El primer par se forma con los índices 1 y 4, y el segundo par se forma con los índices 2 y 5. La diferencia máxima es max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1. Por lo tanto, devolvemos 1.

Ejemplo 2:

Input: nums = [4,2,1,2], p = 1 Output: 0 Explicación: Dejemos que los índices 1 y 3 formen un par. La diferencia de ese par es |2 - 2| = 0, que es el mínimo que podemos obtener.

Soluciones

Python
lass Solution:
    def isPossible(self, nums, val, p):
        count = 0
        i = 1
        while i < len(nums):
            if nums[i] - nums[i - 1] <= val:
                count += 1
                i += 2
            else:
                i += 1
        return count >= p

    def minimizeMax(self, nums, p):
        nums.sort()
        low, high = 0, nums[-1]
        ans = float('inf')
        while low <= high:
            mid = low + (high - low) // 2
            if self.isPossible(nums, mid, p):
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        return ans
BUSCARCtrl K