2616. Minimize the Maximum Difference of Pairs (binary search idea

T: O(nlogn)
S: O(1)

```java
class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums[nums.length-1] - nums[0];

        while (left < right) {
            int mid = left + (right - left)/2;
            //System.out.println("mid:" + mid);
            int pairCount = 0;
            for (int i = 0; i < nums.length-1; i++) {
                if (nums[i+1] - nums[i] <= mid) {
                    pairCount++;
                    i++; // jump to next pair index (choose this i and i+1 pair)
                }
            }
            if (pairCount >= p) {
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return left;
    }
}

/*
T: O(nlogn)
S: O(1)

 0  1 2 3 4 5
[10,1,2,7,1,3]


find pair 
then return maximum diff

find all pair -> O(n^2)
cal diff and sort asc -> nlogn
find max diff of pair -> O(p)
anyway it doesn't work. 

how to reduce find all pair?

or how to find small diff quickly?

sort?

[10,1,2,7,1,3]

1,1,2,3,7,10

0~9
left = 0
right = 9

0        4         9
-------------------
0      3
    1  right

mid = 0 + 9/2 = 4
p = [1,1], [2,3], [7,10]

right = mid - 1 = 4 - 1 = 3
mid = 0 + 3/2 = 1
p= [1,1], [2,3]

right = mid - 1 = 0
mid = 0
p = [1,1]

pCount < p
left = mid + 1 = 1
---> left > right -> end

return left
  

  so it ok to return left when using left <= right


  so...I think I'll use left < right in the future, because it can return left or right, all is ok
*/
```

有問題的code

```java
從題意, 會覺得, 那我就 sort, 然後算出各個 diff
在 sort diff, 取前 p 個, 不就是答案嗎 但這樣是有問題的

[3,4,2,3,2,1,2]

why this can't, because it reuse the "index"
1 2 2 2 3 3 4
 1 0 0 1 0 1
   選了 index 0 的 0
   下個 2 2 就不能再用了

   2 2 2
    0 0.  -> 只能選其中一個0

所以這樣sort diff 挑前幾個, 是會重複用到 index 的 ->不可行


本題關鍵在於, sort 後, 選了某對(鄰居)我就可以跳到下個了 greedy 的想法, 
因為如果今天我不挑鄰居, 並不能產生較小的 diff, 因為 sort 後的鄰居, 才能得到小 diff


class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);

        List<Integer> diff = new ArrayList<>();
        for (int i = 0; i < nums.length-1;i++) {
            diff.add(Math.abs(nums[i] - nums[i+1]));
        }
        Collections.sort(diff);
        int result = 0;
        for (int i = 0; i < p; i++) {
            result = Math.max(result, diff.get(i));
        }
        return result;
    }
}

/*
[10,1,2,7,1,3], p = 2
```



```

new version

```java
class Solution {
    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);

        int left = 0;
        int right = nums[nums.length-1] - nums[0];

        int result = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = left + (right - left)/2;
            int pCount = 0;
            for (int i = 0; i < nums.length-1; i++) {
                if (nums[i+1] - nums[i] <= mid) {
                    pCount++;
                    i++;
                }
            }
            if (pCount >= p) {
                result = Math.min(result, mid);
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }
}

/*
[10,1,2,7,1,3], p = 2

[3,4,2,3,2,1,2]

why this can't, because it reuse the "index"
1 2 2 2 3 3 4
 1 0 0 1 0 1
   選了 index 0 的 0
   下個 2 2 就不能再用了

   2 2 2
    0 0.  -> 只能選其中一個0

所以這樣sort diff 挑前幾個, 是會重複用到 index 的 不可行

1 1 2 3 7 10
 0 1 1 4 3
*/
```