Maximize Score of Numbers in Ranges

Med

#2912Time: O(N! * N * log R), where `N` is the number of intervals and `R` is the search range for the score. This is computationally infeasible.Space: O(N) for storing the permutation and recursion stack.

Patterns

Greedy

Algorithms

Binary Search Sorting

Data structures

Array

Prompt

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 i^th integer must belong to the i^th 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.

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⁵
0 <= start[i] <= 10⁹
0 <= d <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach tackles the problem by exploring every possible ordering of intervals. For a given potential score k, it checks if there exists any permutation of the n intervals that allows for choosing n numbers with a minimum difference of k. This check is then used within a binary search framework to find the maximum possible score.

Algorithm

The problem of finding the maximum score can be solved by binary searching for the score k.
To check if a score k is achievable (check(k)), we must determine if there's an ordering of intervals that allows for a valid selection of numbers.
A brute-force method for check(k) is to try all n! permutations of the intervals.
For each permutation p = (p_0, p_1, ..., p_{n-1}), greedily select the smallest possible numbers c_{p_i} that satisfy the constraints c_{p_i} >= c_{p_{i-1}} + k and c_{p_i} is in its interval.
If any permutation allows for a valid selection, check(k) returns true.
If all n! permutations fail, check(k) returns false.

Walkthrough

The core of this method is to solve the decision problem: "Is a score of k achievable?" A brute-force way to answer this is to consider every possible sequence in which we can pick numbers from the intervals. There are n! such sequences (permutations).

For each permutation of the intervals, we can greedily try to assign the smallest possible numbers. We iterate through the permuted intervals, and for each one, we choose the smallest valid number that is at least k greater than the number chosen for the previous interval in the permutation. If we can successfully assign numbers for an entire permutation, then the score k is achievable.

This entire checking process is wrapped in a binary search over the possible range of scores to find the maximum k for which the check returns true.

1import java.util.Arrays;2import java.util.Collections;3import java.util.ArrayList;4import java.util.List;5 6class Solution {7    // This approach is too slow and will time out, presented for theoretical purposes.8    public int maximizeScore(int[] start, int d) {9        int n = start.length;10        List<Integer> p = new ArrayList<>();11        for (int i = 0; i < n; i++) {12            p.add(i);13        }14 15        long low = 0, high = 2_000_000_000L, ans = 0;16 17        while (low <= high) {18            long mid = low + (high - low) / 2;19            if (check(mid, start, d, n)) {20                ans = mid;21                low = mid + 1;22            } else {23                high = mid - 1;24            }25        }26        return (int) ans;27    }28 29    private boolean check(long k, int[] start, int d, int n) {30        List<Integer> p = new ArrayList<>();31        for (int i = 0; i < n; i++) {32            p.add(i);33        }34        return permutations(p, 0, start, d, k);35    }36 37    private boolean permutations(List<Integer> p, int startIdx, int[] start, int d, long k) {38        if (startIdx == p.size()) {39            return checkPermutation(p, start, d, k);40        }41        for (int i = startIdx; i < p.size(); i++) {42            Collections.swap(p, i, startIdx);43            if (permutations(p, startIdx + 1, start, d, k)) {44                return true;45            }46            Collections.swap(p, i, startIdx); // backtrack47        }48        return false;49    }50 51    private boolean checkPermutation(List<Integer> p, int[] start, int d, long k) {52        long lastVal = -2_000_000_000_000_000_000L; // A very small number53        for (int index : p) {54            long s = start[index];55            long e = s + d;56            long currentVal = Math.max(s, lastVal + k);57            if (currentVal > e) {58                return false;59            }60            lastVal = currentVal;61        }62        return true;63    }64}

Complexity

Time

O(N! * N * log R), where `N` is the number of intervals and `R` is the search range for the score. This is computationally infeasible.

Space

O(N) for storing the permutation and recursion stack.

Trade-offs

Pros

Conceptually simple as it directly models the problem of trying all orderings.

Cons

Extremely inefficient due to the factorial complexity.
Only feasible for very small n (e.g., n <= 10), which is far below the problem constraints.

This efficient approach combines binary search on the answer with a greedy strategy. The problem is reframed as finding the largest k for which we can answer the question: "Is it possible to achieve a score of at least k?". This decision problem can be solved efficiently by sorting the intervals by their start times and greedily choosing the smallest possible valid number for each interval in that order.

Algorithm

The problem of maximizing a minimum value is a classic pattern for binary search on the answer. We binary search for the score k.
To efficiently check if a score k is achievable (can_achieve(k)), we use a greedy strategy.
Sort the intervals based on their start points. This is the key insight.
Iterate through the sorted intervals. For each interval, greedily pick the smallest possible number that is valid.
The chosen number for the current interval [s, e] must be at least k greater than the number chosen for the previous interval. So, the candidate choice is max(s, last_chosen_value + k).
If this candidate choice is greater than e, it's impossible to achieve score k. Return false.
If we can find a valid number for all intervals, return true.
The initial sort is done once, making each can_achieve(k) check an O(N) operation.

Walkthrough

The optimal strategy involves binary searching for the maximum possible score. Let's say we want to check if a score k is achievable. This subproblem can be solved greedily.

The crucial insight is to process the intervals in a specific order. If we sort the intervals based on their start points, we can make a greedy choice at each step. We iterate through the sorted intervals and for each interval [start[i], start[i] + d], we must select a number c_i.

To maximize our chances of success for subsequent intervals, we should choose c_i to be as small as possible. The chosen number c_i must be at least k greater than the number chosen for the previous interval in the sorted list (last_chosen_value). It must also be within its own interval, so c_i >= start[i]. Combining these, the smallest possible value for c_i is max(start[i], last_chosen_value + k).

We then check if this smallest possible choice is valid, i.e., if it's less than or equal to start[i] + d. If this condition fails for any interval, it's impossible to achieve a score of k, and the check fails. If we successfully find a number for every interval, the score k is achievable.

The overall algorithm first sorts the intervals (as pairs of start and end points), then performs a binary search on the score k, using this greedy O(N) check at each step.

1import java.util.Arrays;2 3class Solution {4    class Interval {5        long start, end;6        Interval(long start, long end) {7            this.start = start;8            this.end = end;9        }10    }11 12    public int maximizeScore(int[] start, int d) {13        int n = start.length;14        Interval[] intervals = new Interval[n];15        for (int i = 0; i < n; i++) {16            intervals[i] = new Interval(start[i], (long)start[i] + d);17        }18 19        Arrays.sort(intervals, (a, b) -> Long.compare(a.start, b.start));20 21        long low = 0, high = 2_000_000_000L, ans = 0;22 23        while (low <= high) {24            long mid = low + (high - low) / 2;25            if (canAchieve(mid, intervals, n)) {26                ans = mid;27                low = mid + 1;28            } else {29                high = mid - 1;30            }31        }32        return (int) ans;33    }34 35    private boolean canAchieve(long k, Interval[] intervals, int n) {36        long lastChosenValue = -3_000_000_000L; // A very small number, smaller than any possible choice37 38        for (int i = 0; i < n; i++) {39            long currentChoice = Math.max(intervals[i].start, lastChosenValue + k);40            if (currentChoice > intervals[i].end) {41                return false;42            }43            lastChosenValue = currentChoice;44        }45        return true;46    }47}

Complexity

Time

O(N log N + N log R), where `N` is the number of intervals and `R` is the search range for the score. The `O(N log N)` term comes from the initial sort, and `O(N log R)` from the binary search where each check takes `O(N)`.

Space

O(N) to store the intervals for sorting.

Trade-offs

Pros

Highly efficient and passes within time limits.
The greedy strategy is proven to be optimal for the check function.
The binary search approach is standard for this type of max-min problem.

Cons

Requires careful handling of large numbers (using long) to prevent overflow.

Solutions

Solution

1class Solution {2private3  int[] start;4private5  int d;6public7  int maxPossibleScore(int[] start, int d) {8    Arrays.sort(start);9    this.start = start;10    this.d = d;11    int n = start.length;12    int l = 0, r = start[n - 1] + d - start[0];13    while (l < r) {14      int mid = (l + r + 1) >>> 1;15      if (check(mid)) {16        l = mid;17      } else {18        r = mid - 1;19      }20    }21    return l;22  }23private24  boolean check(int mi) {25    long last = Long.MIN_VALUE;26    for (int st : start) {27      if (last + mi > st + d) {28        return false;29      }30      last = Math.max(st, last + mi);31    }32    return true;33  }34}

1class Solution {2public:3  int maxPossibleScore(vector<int> &start, int d) {4    ranges ::sort(start);5    auto check = [&](int mi) -> bool {6      long long last = LLONG_MIN;7      for (int st : start) {8        if (last + mi > st + d) {9          return false;10        }11        last = max((long long)st, last + mi);12      }13      return true;14    };15    int l = 0, r = start.back() + d - start[0];16    while (l < r) {17      int mid = l + (r - l + 1) / 2;18      if (check(mid)) {19        l = mid;20      } else {21        r = mid - 1;22      }23    }24    return l;25  }26};

1class Solution:2    def maxPossibleScore(self, start: List[int], d: int) -> int: def check(mi: int) -> bool: last = - inf for st in start: if last + mi > st + d: return False last = max(st, last + mi) return True start . sort() l, r = 0, start[- 1] + d - start[0] while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return l

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem