# Maximize Score of Numbers in Ranges
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-score-of-numbers-in-ranges)
Canonical: https://scaleengineer.com/dsa/problems/maximize-score-of-numbers-in-ranges
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
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 <= 105`
* `0 <= start[i] <= 109`
* `0 <= d <= 109`

# Approaches
## Brute Force by Trying All Permutations
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Binary Search on Score with a Greedy Check
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Arrays;

class Solution {
    class Interval {
        long start, end;
        Interval(long start, long end) {
            this.start = start;
            this.end = end;
        }
    }

    public int maximizeScore(int[] start, int d) {
        int n = start.length;
        Interval[] intervals = new Interval[n];
        for (int i = 0; i < n; i++) {
            intervals[i] = new Interval(start[i], (long)start[i] + d);
        }

        Arrays.sort(intervals, (a, b) -> Long.compare(a.start, b.start));

        long low = 0, high = 2_000_000_000L, ans = 0;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (canAchieve(mid, intervals, n)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return (int) ans;
    }

    private boolean canAchieve(long k, Interval[] intervals, int n) {
        long lastChosenValue = -3_000_000_000L; // A very small number, smaller than any possible choice

        for (int i = 0; i < n; i++) {
            long currentChoice = Math.max(intervals[i].start, lastChosenValue + k);
            if (currentChoice > intervals[i].end) {
                return false;
            }
            lastChosenValue = currentChoice;
        }
        return true;
    }
}
```
### 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.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxPossibleScore(vector<int> &start, int d) {
    ranges ::sort(start);
    auto check = [&](int mi) -> bool {
      long long last = LLONG_MIN;
      for (int st : start) {
        if (last + mi > st + d) {
          return false;
        }
        last = max((long long)st, last + mi);
      }
      return true;
    };
    int l = 0, r = start.back() + d - start[0];
    while (l < r) {
      int mid = l + (r - l + 1) / 2;
      if (check(mid)) {
        l = mid;
      } else {
        r = mid - 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    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

```