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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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

  1. Sort the start array.
  2. Use binary search for the answer between 0 and the maximum possible difference.
  3. 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.
  4. If possible for all intervals, try a larger value; otherwise, try smaller.
  5. Return the largest value for which it is possible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maximizeScore(vector<int>& start, int d) {
        int n = start.size();
        sort(start.begin(), start.end());
        int l = 0, r = 1e9, ans = 0;
        while (l <= r) {
            int m = l + (r-l)/2, prev = start[0];
            bool ok = true;
            for (int i = 1; i < n; ++i) {
                int nxt = max(prev + m, start[i]);
                if (nxt > start[i] + d) { ok = false; break; }
                prev = nxt;
            }
            if (ok) { ans = m; l = m+1; }
            else r = m-1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func maximizeScore(start []int, d int) int {
    sort.Ints(start)
    n := len(start)
    l, r, ans := 0, int(1e9), 0
    for l <= r {
        m := (l + r) / 2
        prev := start[0]
        ok := true
        for i := 1; i < n; i++ {
            nxt := prev + m
            if nxt < start[i] {
                nxt = start[i]
            }
            if nxt > start[i]+d {
                ok = false
                break
            }
            prev = nxt
        }
        if ok {
            ans = m
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int maximizeScore(int[] start, int d) {
        Arrays.sort(start);
        int n = start.length, l = 0, r = (int)1e9, ans = 0;
        while (l <= r) {
            int m = l + (r-l)/2, prev = start[0];
            boolean ok = true;
            for (int i = 1; i < n; i++) {
                int nxt = Math.max(prev + m, start[i]);
                if (nxt > start[i] + d) { ok = false; break; }
                prev = nxt;
            }
            if (ok) { ans = m; l = m+1; }
            else r = m-1;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    fun maximizeScore(start: IntArray, d: Int): Int {
        start.sort()
        var l = 0
        var r = 1_000_000_000
        var ans = 0
        while (l <= r) {
            val m = (l + r) / 2
            var prev = start[0]
            var ok = true
            for (i in 1 until start.size) {
                var nxt = maxOf(prev + m, start[i])
                if (nxt > start[i] + d) {
                    ok = false
                    break
                }
                prev = nxt
            }
            if (ok) {
                ans = m
                l = m + 1
            } else {
                r = m - 1
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def maximizeScore(self, start: list[int], d: int) -> int:
        start.sort()
        n = len(start)
        l, r, ans = 0, 10**9, 0
        while l <= r:
            m = (l + r) // 2
            prev = start[0]
            ok = True
            for i in range(1, n):
                nxt = max(prev + m, start[i])
                if nxt > start[i] + d:
                    ok = False
                    break
                prev = nxt
            if ok:
                ans = m
                l = m + 1
            else:
                r = m - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn maximize_score(mut start: Vec<i32>, d: i32) -> i32 {
        start.sort();
        let n = start.len();
        let (mut l, mut r, mut ans) = (0, 1_000_000_000, 0);
        while l <= r {
            let m = (l + r) / 2;
            let mut prev = start[0];
            let mut ok = true;
            for i in 1..n {
                let nxt = prev + m;
                let nxt = nxt.max(start[i]);
                if nxt > start[i] + d {
                    ok = false;
                    break;
                }
                prev = nxt;
            }
            if ok {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    maximizeScore(start: number[], d: number): number {
        start.sort((a, b) => a - b);
        let l = 0, r = 1e9, ans = 0;
        while (l <= r) {
            let m = Math.floor((l + r) / 2), prev = start[0], ok = true;
            for (let i = 1; i < start.length; i++) {
                let nxt = Math.max(prev + m, start[i]);
                if (nxt > start[i] + d) { ok = false; break; }
                prev = nxt;
            }
            if (ok) { ans = m; l = m + 1; }
            else r = m - 1;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log X) — where X is the search range (up to 1e9), and n is the number of intervals.
  • 🧺 Space complexity: O(1) — only a few variables are used.