题目描述

给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。

你需要选择 n 个整数，其中第 i 个整数必须属于第 i 个区间。所选整数的 得分 定义为所选整数两两之间的 最小 绝对差。

返回所选整数的 最大可能得分。

样例

输入： start = [6,0,3], d = 2

输出： 4

解释：

可以选择整数 8, 0 和 4 获得最大可能得分，
    得分为 min(|8 - 0|, |8 - 4|, |0 - 4|)，等于 4。

输入： start = [2,6,13,13], d = 5

输出： 5

解释：

可以选择整数 2, 7, 13 和 18 获得最大可能得分，
    得分为 min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|)，等于 5。

限制

• 2 <= start.length <= 10^5
• 0 <= start[i] <= 10^9
• 0 <= d <= 10^9

算法

(二分答案，贪心) $O(n \log n + n \log m)$

1. 求最大的最小间隔，可以使用二分答案的思路。令最小间隔为 $p$，判断是否有合法的选择方式。
2. 将整数区间从小到大排序。
3. 判断时，按顺序遍历所有整数区间。如果选择区间的终点都无法满足最小间隔大于等于 $p$，则校验失败。否则，选择区间起点和上一次数字加 $p$ 中的较大值。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 二分的区间范围为 $[0, m]$，其中 $m$ 是最大可能的答案，这里为 $2 * 10^9$。
• 判断的时间复杂度为常数。
• 故总时间复杂度为 $O(n \log n + n \log m)$。

空间复杂度

• 需要 $O(\log n)$ 的额外空间存储排序的系统栈。

C++ 代码

class Solution {
private:
    int n;

    bool check(int p, const vector<int> &start, int d) {
        int c = start[0];

        for (int i = 1; i < n; i++) {
            if (start[i] + d - c < p)
                return false;

            c = max(start[i], c + p);
        }

        return true;
    }

public:
    int maxPossibleScore(vector<int>& start, int d) {
        n = start.size();

        sort(start.begin(), start.end());

        int l = 0, r = 2000000000;
        while (l < r) {
            int mid = l + (r - l) / 2;

            if (check(mid + 1, start, d)) l = mid + 1;
            else r = mid;
        }

        return l;
    }
};