Maximize Score of Numbers in Ranges

Maximize Score of Numbers in Ranges

What is this problem about?

In this problem, you are given an array of integers representing the starting points of intervals. Each interval has the same length, defined by an integer d. This means for each integer start in the array, you have an interval [start, start + d]. You must pick exactly one integer from each interval. Your goal is to maximize the minimum absolute difference between any two of your chosen integers.

Why is this asked in interviews?

This is an advanced optimization problem that perfectly maps to the "Maximize the Minimum" archetype. Companies ask it to test if a candidate can implement Binary Search on the Answer. It evaluates whether you can combine an abstract search space (the answer itself) with a greedy validation function (placing numbers chronologically).

Algorithmic pattern used

This problem is solved using Binary Search on the Answer paired with a Greedy validator.

1. Sort the starts array.
2. Define your search space for the "minimum difference". The lowest possible difference is 0. The highest possible difference is (max_start + d) - min_start.
3. Perform a Binary Search. For a guessed difference mid, use a Greedy function to see if it's possible to pick numbers from every interval such that every number is at least mid apart.
4. Greedy logic: Pick the smallest possible valid number in the first interval. For the next interval, pick the smallest valid number that is $\ge \text{last\_picked} + mid$. If this required number exceeds start + d, the guess mid is invalid.

Example explanation

Starts: [1, 5, 8], d = 2. Intervals are [1, 3], [5, 7], [8, 10]. Sorted: [1, 5, 8]. Let's test a guessed difference mid = 3.

• Interval 1 [1, 3]: Greedily pick the smallest: 1.
• Interval 2 [5, 7]: We must pick a number $\ge 1 + 3 = 4$. The interval is [5, 7], so the smallest valid choice is 5.
• Interval 3 [8, 10]: We must pick a number $\ge 5 + 3 = 8$. The interval is [8, 10], so the smallest valid choice is 8. All numbers picked successfully! We achieved a difference of 3. We can adjust our binary search to try mid = 4 to see if we can do better.

Common mistakes candidates make

A common error is overcomplicating the greedy choice inside the validation function. Some candidates try to pick numbers from the middle of the interval or delay decisions. The mathematically sound approach is to be ruthlessly greedy: always pick the absolute smallest number allowed by the constraints. Leaving as much "runway" as possible for subsequent intervals is the only way to maximize success.

Interview preparation tip

When tackling the Maximize Score of Numbers in Ranges coding problem, the phrase "maximize the minimum difference" should instantly trigger muscle memory for Binary Search. Practice writing the isValid(mid) helper function. It is a simple $O(N)$ loop that tracks last_picked_value = max(current_start, last_picked_value + mid). If last_picked_value exceeds current_start + d, return false. This template solves dozens of hard optimization problems.