Maximize Score of Numbers in Ranges
MedPrompt
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.
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 <= 1050 <= start[i] <= 1090 <= d <= 109
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
kis 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 alln!permutations of the intervals. - For each permutation
p = (p_0, p_1, ..., p_{n-1}), greedily select the smallest possible numbersc_{p_i}that satisfy the constraintsc_{p_i} >= c_{p_{i-1}} + kandc_{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.
import java.util.Arrays;import java.util.Collections;import java.util.ArrayList;import java.util.List; class Solution { // This approach is too slow and will time out, presented for theoretical purposes. public int maximizeScore(int[] start, int d) { int n = start.length; List<Integer> p = new ArrayList<>(); for (int i = 0; i < n; i++) { p.add(i); } long low = 0, high = 2_000_000_000L, ans = 0; while (low <= high) { long mid = low + (high - low) / 2; if (check(mid, start, d, n)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return (int) ans; } private boolean check(long k, int[] start, int d, int n) { List<Integer> p = new ArrayList<>(); for (int i = 0; i < n; i++) { p.add(i); } return permutations(p, 0, start, d, k); } private boolean permutations(List<Integer> p, int startIdx, int[] start, int d, long k) { if (startIdx == p.size()) { return checkPermutation(p, start, d, k); } for (int i = startIdx; i < p.size(); i++) { Collections.swap(p, i, startIdx); if (permutations(p, startIdx + 1, start, d, k)) { return true; } Collections.swap(p, i, startIdx); // backtrack } return false; } private boolean checkPermutation(List<Integer> p, int[] start, int d, long k) { long lastVal = -2_000_000_000_000_000_000L; // A very small number for (int index : p) { long s = start[index]; long e = s + d; long currentVal = Math.max(s, lastVal + k); if (currentVal > e) { return false; } lastVal = currentVal; } return true; }}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.
Solutions
Solution
class Solution {private int[] start;private int d;public int maxPossibleScore(int[] start, int d) { Arrays.sort(start); this.start = start; this.d = d; int n = start.length; int l = 0, r = start[n - 1] + d - start[0]; while (l < r) { int mid = (l + r + 1) >>> 1; if (check(mid)) { l = mid; } else { r = mid - 1; } } return l; }private boolean check(int mi) { long last = Long.MIN_VALUE; for (int st : start) { if (last + mi > st + d) { return false; } last = Math.max(st, last + mi); } return true; }}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.