Maximize Score of Numbers in Ranges - Practice Coding Problems

Maximize Score of Numbers in Ranges - 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 i-th integer must belong to the i-th 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.

Input & Output

Example 1 — Basic Case

$ Input: start = [4, 6, 8], d = 2

› Output: 2

💡 Note: Intervals are [4,6], [6,8], [8,10]. We can choose integers 4, 6, 8 with minimum difference = min(|6-4|, |8-6|, |8-4|) = min(2, 2, 4) = 2

Example 2 — Same Start Points

$ Input: start = [2, 6, 8], d = 0

› Output: 0

💡 Note: With d=0, each interval contains only one integer: [2,2], [6,6], [8,8]. We must choose 2, 6, 8 with minimum difference = min(|6-2|, |8-6|, |8-2|) = min(4, 2, 6) = 2

Example 3 — Overlapping Intervals

$ Input: start = [6, 13, 18], d = 10

› Output: 3

💡 Note: Intervals are [6,16], [13,23], [18,28]. Optimal selection might be 6, 16, 19 giving minimum difference = min(|16-6|, |19-16|, |19-6|) = min(10, 3, 13) = 3

Constraints

1 ≤ start.length ≤ 10⁴
0 ≤ start[i] ≤ 10⁸
0 ≤ d ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given intervals [4,6], [6,8], [8,10]

Process

Select one integer from each interval to maximize minimum difference

Output

Optimal selection gives maximum score = 2

Key Takeaway

🎯 Key Insight: Use binary search on the answer space to efficiently find the maximum achievable minimum difference

Asked in

G Google 15 a Amazon 12 f Meta 8

The key insight is to use binary search on the answer space combined with greedy validation. Sort intervals by start position, then binary search on possible score values. For each candidate score, greedily place integers to maintain minimum differences. Best approach is Binary Search on Answer with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O((d+1)ⁿ × n²)	O(n)	Try all possible combinations of integers from each interval
Binary Search on Answer	O(n log n + n log(max_range))	O(n)	Binary search on the possible score values, check if each score is achievable

Brute Force — Algorithm Steps

Step 1: Generate all combinations of choosing one integer from each interval
Step 2: For each combination, calculate minimum absolute difference between any two integers
Step 3: Return the maximum score found across all combinations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Try every possible selection from each interval

Calculate Scores

For each combination, find minimum pairwise difference

Track Maximum

Keep the highest score found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int maxScore = 0;

void backtrack(int* start, int n, int d, int index, int* chosen) {
    if (index == n) {
        int minDiff = INT_MAX;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = abs(chosen[i] - chosen[j]);
                if (diff < minDiff) minDiff = diff;
            }
        }
        if (minDiff > maxScore) maxScore = minDiff;
        return;
    }
    
    for (int val = start[index]; val <= start[index] + d; val++) {
        chosen[index] = val;
        backtrack(start, n, d, index + 1, chosen);
    }
}

int solution(int* start, int n, int d) {
    maxScore = 0;
    int* chosen = (int*)malloc(n * sizeof(int));
    backtrack(start, n, d, 0, chosen);
    free(chosen);
    return maxScore;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int start[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            start[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int d;
    scanf("%d", &d);
    
    printf("%d\n", solution(start, n, d));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((d+1)ⁿ × n²)

(d+1)^n combinations, each requiring O(n²) pairwise comparisons

⚠ Quadratic Growth

Space Complexity

O(n)

Storage for current combination of n chosen integers

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~35 min Avg. Time

580 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler