"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:T1dbc,

Problem

You are given an array of integers start and an integer d, representing n intervals [start[i], start[i] + d].

You are asked to choose n integers where the ith integer must belong to the ith interval. The score of the chosen integers is defined as the minimum absolute difference between any two integers that have been chosen.

Return the maximum possible score of the chosen integers.

Examples

Example 1


Input: start = [6,0,3], d = 2

Output: 4

Explanation:

The maximum possible score can be obtained by choosing integers: 8, 0, and 4.
The score of these chosen integers is `min(|8 - 0|, |8 - 4|, |0 - 4|)` which
equals 4.

Example 2


Input: start = [2,6,13,13], d = 5

Output: 5

Explanation:

The maximum possible score can be obtained by choosing integers: 2, 7, 13, and
18. The score of these chosen integers is `min(|2 - 7|, |2 - 13|, |2 - 18|, |7
- 13|, |7 - 18|, |13 - 18|)` which equals 5.

Constraints

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

Solution

Method 1 – Binary Search with Greedy Placement

Intuition

To maximize the minimum difference between chosen numbers, we can use binary search on the answer. For each candidate difference, we greedily try to pick numbers from each interval such that each is at least that far apart from the previous.

Approach

Sort the start array.
Use binary search for the answer between 0 and the maximum possible difference.
For each mid value, try to greedily pick numbers from each interval:
- For the first interval, pick the leftmost value.
- For each next interval, pick the smallest value in its range that is at least mid away from the previous pick.
- If not possible, the candidate is too large.
If possible for all intervals, try a larger value; otherwise, try smaller.
Return the largest value for which it is possible.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maximizeScore(vector<int>& start, int d) {\n        int n = start.size();\n        sort(start.begin(), start.end());\n        int l = 0, r = 1e9, ans = 0;\n        while (l <= r) {\n            int m = l + (r-l)/2, prev = start[0];\n            bool ok = true;\n            for (int i = 1; i < n; ++i) {\n                int nxt = max(prev + m, start[i]);\n                if (nxt > start[i] + d) { ok = false; break; }\n                prev = nxt;\n            }\n            if (ok) { ans = m; l = m+1; }\n            else r = m-1;\n        }\n        return ans;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func maximizeScore(start []int, d int) int {\n    sort.Ints(start)\n    n := len(start)\n    l, r, ans := 0, int(1e9), 0\n    for l <= r {\n        m := (l + r) / 2\n        prev := start[0]\n        ok := true\n        for i := 1; i < n;

Related Tags