Watch 10 video solutions for Maximize Score of Numbers in Ranges, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by codi has 2,001 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |