Skip to main content
Back to problems
#3281
Medium Algorithms

Maximize score of numbers in ranges

Array Binary Search Greedy Sorting
35.6% acceptance
Feb 25, 2026
223
50
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 chosen. Return the maximum possible score of the chosen integers.

Solution

Rust
Time O(n log n)
Space O(1)
LeetCode
solution.rs 
impl Solution {
  pub fn max_possible_score(mut start: Vec<i32>, d: i32) -> i32 {
    start.sort();
    let n = start.len();
    let d = d as i64;
    // Binary search on the answer (minimum gap)
    let feasible = |gap: i64| -> bool {
      // Greedily assign each interval's chosen value as small as possible
      // but at least prev + gap
      let mut prev = start[0] as i64;
      for i in 1..n {
        let next = (prev + gap).max(start[i] as i64);
        if next > start[i] as i64 + d {
          return false;
        }
        prev = next;
      }
      true
    };
    let mut lo = 0i64;
    let mut hi = (start[n - 1] as i64 + d - start[0] as i64) / (n as i64 - 1) + 1;
    while lo < hi {
      let mid = (lo + hi + 1) / 2;
      if feasible(mid) {
        lo = mid;
      } else {
        hi = mid - 1;
      }
    }
    lo as i32
  }
}