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 <= 109Problem Overview: You are given multiple numeric ranges. From each range, you must pick exactly one number. The goal is to maximize the minimum difference between any two chosen numbers after ordering them. This turns the task into spacing selections as far apart as possible while staying inside each interval.
Approach 1: Greedy Selection from Intervals (O(n log n) time, O(1) space)
Sort the ranges by their starting value using sorting. Then iterate through the intervals and always pick the smallest feasible number that keeps the difference from the previously chosen number as large as possible. The greedy rule is simple: choose max(range_start, prev + diff) while ensuring the value does not exceed the interval's end. This works because selecting the earliest valid number leaves the most room for later intervals. The approach relies on interval ordering and greedy placement to maintain spacing.
Approach 2: Binary Search for Optimal Difference (O(n log n + n log D) time, O(1) space)
The optimal solution uses binary search on the answer. Instead of directly maximizing the score, guess a candidate minimum difference d. Then verify if it's possible to pick numbers from each interval such that every chosen value is at least d apart. The feasibility check runs greedily: iterate through sorted intervals and place the earliest allowed value that is ≥ prev + d. If the value exceeds the interval end, the candidate difference is impossible. Because feasibility is monotonic (if d works, smaller values also work), binary search efficiently finds the largest valid difference.
The greedy feasibility check leverages the ordered structure of intervals and ensures each placement keeps future choices flexible. This pattern—binary searching the answer while validating with a greedy pass—is common in spacing problems involving arrays, greedy strategies, and interval constraints.
Recommended for interviews: The binary search on the answer combined with a greedy feasibility check is the approach most interviewers expect. It demonstrates understanding of monotonic properties and interval placement. Implementing the greedy check first helps validate the idea, while the binary search layer shows algorithmic optimization.
This approach leverages a simple greedy strategy to select the number at the upper bound of each interval if possible. This choice maximizes the subsequent space for the next interval and hence the difference between the numbers chosen from consecutive intervals.
Sorting the intervals from smallest to largest ensures that we're optimizing space allocation sequentially.
The implementation sorts the array of start points and then iterates through the start points to determine the minimum difference required to keep all choices within the respective intervals. Since the intervals are sorted, any potential increasing pattern is accounted for by finding the difference across consecutive points adjusted for the interval spread.
Time Complexity: O(n log n) due to sorting
Space Complexity: O(1) as we sort in place.
This approach leverages binary search to identify the maximum score possible through repeatedly checking if a specific minimum difference is feasible. Adjusting the range and verifying selections ensures a balanced computational load while persistently searching for the exact maximum.
Binary search allows pruning of feasible solutions, narrowing results efficiently.
This method checks feasibility of a given minimum distance using a binary search pattern. By evaluating if selections remain within bounds and still approximate a candidate score, this optimizes towards the highest valid solution.
Time Complexity: O(n log(maxDifference)) combining sorting and binary search iterations.
Space Complexity: O(1) - no additional storage apart from input modification.
We can first sort the start array. Then, we consider selecting integers from left to right, where the score is equal to the minimum difference between any two adjacent selected integers.
If a difference x satisfies the condition, then any x' < x will also satisfy the condition. Therefore, we can use binary search to find the largest difference that satisfies the condition.
We define the left boundary of the binary search as l = 0 and the right boundary as r = start[-1] + d - start[0]. Each time, we take the middle value mid = \left\lfloor \frac{l + r + 1}{2} \right\rfloor and check whether it satisfies the condition.
We define a function check(mi) to determine whether the condition is satisfied, implemented as follows:
last = -infty, representing the last selected integer.start array. If last + mi > st + d, it means we cannot select the integer st, and we return false. Otherwise, we update last = max(st, last + mi).start array and all conditions are satisfied, we return true.The time complexity is O(n times log M), where n and M are the length and the maximum value of the start array, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Selection from Intervals | Time Complexity: O(n log n) due to sorting |
| Binary Search for Optimal Difference | Time Complexity: O(n log(maxDifference)) combining sorting and binary search iterations. |
| Sorting + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Selection from Intervals | O(n log n) | O(1) | When verifying feasibility of placements or building the greedy core logic for interval selection |
| Binary Search for Optimal Difference | O(n log n + n log D) | O(1) | General case to maximize the minimum distance between chosen values across ranges |
Maximize Score of Numbers in Ranges || LeetCode Weekly Contest 414 || Leetcode Solution • codi • 2,001 views views
Watch 9 more video solutions →Practice Maximize Score of Numbers in Ranges with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor