3281. Maximize Score of Numbers in Ranges

Problem Description

You are given an array of integers start and an integer d, which represent n intervals [start[i], start[i] + d]. You need to select n integers such that the i-th integer belongs to the i-th interval. The score of the chosen integers is the minimum absolute difference between any two integers among those selected. Your task is to return the maximum possible score of the chosen integers.

Intuition

The problem requires selecting a number from each given interval while maximizing the smallest difference between any two chosen numbers. To achieve this, it is beneficial to sort the start array, which helps in determining the feasibility of selecting numbers with a specific minimum difference.

Here's the reasoning process:

Sorting: By sorting the start array, we can work through the intervals in order, making it easier to apply the difference condition consistently across the selection.
Binary Search: The problem can be approached using binary search since if a certain minimum difference x between the selected numbers is possible, then any difference less than x is certainly possible as well. This characteristic makes binary search a suitable tool to find the largest possible minimum difference.
Check Feasibility: A helper function check(mi) tests whether it is feasible to select numbers with a minimum difference of mi. It:
- Keeps track of the last chosen number.
- Iterates through each interval and checks if the current interval can accommodate selecting a new number such that the difference from the last chosen number is at least mi.
- If successful for all intervals, the current value of mi is feasible.
Binary Search Implementation:
- Initialize the search boundaries with l as 0 and r as start[-1] + d - start[0] (the maximum span required to calculate the difference).
- Perform binary search to find the maximum possible value of mi by iteratively narrowing the search space based on whether the current middle value mid can be a possible solution.

Through this approach, the solution efficiently finds the maximum possible score by optimizing the selection of numbers within the given constraints.

Learn more about Greedy, Binary Search and Sorting patterns.

Solution Approach

The solution utilizes a combination of sorting and binary search to efficiently determine the maximum possible score of the chosen integers. Here's a step-by-step breakdown:

Sorting the start Array:
- First, the start array is sorted. Sorting is done to ensure that we can methodically evaluate each interval in order and apply the same conditions throughout the array.
Binary Search Setup:
- We define our search boundaries. The left boundary l is initialized to 0 since the minimum difference cannot be negative. The right boundary r is set to start[-1] + d - start[0], which represents the maximum difference between any two selected numbers that is initially possible when considering the entire range.
Binary Search Execution:
- We perform a binary search to find the maximum value of the minimum difference that can be achieved. The middle point mid is calculated using the formula:
```
mid = (l + r + 1) >> 1
```
- The decision to adjust the boundaries is based on whether the check(mid) function returns True or False.
Feasibility Check Function check(mi):
- This function determines if it is possible to select integers such that each consecutive pair of selected integers has a difference of at least mi.
- It maintains a variable last, initialized to negative infinity, as a placeholder for the last selected number.
- Iterates through the sorted start array. For each interval [start[i], start[i] + d], it checks if the potential next number can maintain at least the desired difference mi from the last chosen number.
  - If last + mi > start[i] + d, this means the required difference is not feasible in the current interval and returns False.
  - Otherwise, it updates last to be the maximum of the start of the current interval or the next possible suitable number, ensuring that last maintains the correct sequence.
- If the entire array is traversed without returning False, the function returns True.

In this approach, the correct balance of sorting and binary search allows for an efficient solution to finding the maximum minimum difference possible given the constraints of the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach:

Consider start = [2, 8, 4] and d = 5. This gives us the intervals [2, 7], [8, 13], and [4, 9].

Step 1: Sort the start array

First, sort the start array to get [2, 4, 8].

Step 2: Initialize Binary Search Variables

Set the left boundary l = 0 and the right boundary r = start[-1] + d - start[0] = 11.

Step 3: Begin Binary Search

We will use binary search to find the maximum possible minimum difference (mi).

Iteration 1:
- Calculate mid = (0 + 11 + 1) >> 1 = 6.
- Check feasibility with mi = 6.

Step 4: Feasibility Check for mi = 6

Start with last = -∞.
Interval [2, 7]:
- Choose the starting point since last + mi = -∞ + 6 is less than 2.
- Update last = 2.
Interval [4, 9]:
- last + mi = 2 + 6 = 8 is greater than 9, so it's not feasible.
- check(6) returns False.

Since check(6) is False, set r = 5.

Iteration 2:
- Calculate mid = (0 + 5 + 1) >> 1 = 3.
- Check feasibility with mi = 3.

Feasibility Check for mi = 3

Start with last = -∞.
Interval [2, 7]:
- Choose starting point last = 2.
Interval [4, 9]:
- Choose last = 5.
Interval [8, 13]:
- Choose last = 8.

Since all intervals can accommodate mi = 3, check(3) returns True.

Set l = 3.

Iteration 3:
- Calculate mid = (3 + 5 + 1) >> 1 = 4.
- Check feasibility with mi = 4.

Feasibility Check for mi = 4

Start with last = -∞.
Interval [2, 7]:
- Choose starting point last = 2.
Interval [4, 9]:
- Choose last = 6.
Interval [8, 13]:
- Choose last = 10.

All intervals accommodate mi = 4, so check(4) returns True.

Set l = 4.

Iteration 4:
- Calculate mid = (4 + 5 + 1) >> 1 = 5.
- Check feasibility with mi = 5.

Feasibility Check for mi = 5

Start with last = -∞.
Interval [2, 7]:
- Choose starting point last = 2.
Interval [4, 9]:
- last + 5 = 7, choose last = 7.
Interval [8, 13]:
- Choose last = 12.

Feasibility holds, so check(5) returns True.

Set l = 5.

The binary search concludes with l = 5 as the maximum possible minimum difference. The solution is 5, which is the answer to the problem.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def maxPossibleScore(self, start: List[int], d: int) -> int:
6        def check(mid: int) -> bool:
7            last_position = -inf  # Initialize the last used position to negative infinity
8            for start_time in start:
9                # If the next position cannot be reached with the given distance, return False
10                if last_position + mid > start_time + d:
11                    return False
12                # Update the last position to the maximum of the current start time and potential next position
13                last_position = max(start_time, last_position + mid)
14            return True
15
16        start.sort()  # Sort the start times
17        left, right = 0, start[-1] + d - start[0]  # Set initial boundaries for binary search
18        while left < right:
19            middle = (left + right + 1) >> 1  # Calculate midpoint, favoring right
20            if check(middle):
21                left = middle  # Move the left boundary up if mid is valid
22            else:
23                right = middle - 1  # Move the right boundary down if mid is invalid
24        return left
25

1import java.util.Arrays;
2
3class Solution {
4    private int[] start;
5    private int d;
6
7    public int maxPossibleScore(int[] start, int d) {
8        // Sort the starting positions for more efficient searching.
9        Arrays.sort(start);
10        this.start = start;
11        this.d = d;
12        int n = start.length;
13      
14        // Initialize the binary search boundaries.
15        int left = 0, right = start[n - 1] + d - start[0];
16      
17        // Perform binary search to find the maximum possible score.
18        while (left < right) {
19            // Calculate the middle value with adjustment to avoid overflow.
20            int mid = (left + right + 1) >>> 1;
21          
22            // Check if it's possible to achieve 'mid' as the minimum distance.
23            if (check(mid)) {
24                left = mid; // If possible, try for a larger minimum distance.
25            } else {
26                right = mid - 1; // Otherwise, look for a smaller distance.
27            }
28        }
29      
30        // Return the maximum possible score found.
31        return left;
32    }
33
34    private boolean check(int minDistance) {
35        long lastPosition = Long.MIN_VALUE; // Initialize last position to a very small value.
36      
37        for (int startPoint : start) {
38            // If the last position plus the minimum distance exceeds the current point plus 'd', it's not possible.
39            if (lastPosition + minDistance > startPoint + d) {
40                return false;
41            }
42          
43            // Update the last position to the maximum of the current start or last position plus minDistance.
44            lastPosition = Math.max(startPoint, lastPosition + minDistance);
45        }
46      
47        // If all points can be adjusted according to the conditions, return true.
48        return true;
49    }
50}
51

1#include <vector>
2#include <algorithm>
3#include <climits>
4
5class Solution {
6public:
7    // Function to find the maximum possible score
8    int maxPossibleScore(std::vector<int>& start, int d) {
9        // Sort the 'start' vector for processing
10        std::sort(start.begin(), start.end());
11
12        // Lambda function to check if a minimum score 'mi' is feasible
13        auto isFeasible = [&](int mi) -> bool {
14            long long last = LLONG_MIN; // Initialize the last valid position
15            for (int position : start) {
16                // Check if the current position can be managed with the given 'mi'
17                if (last + mi > position + d) {
18                    return false; // Return false if condition breaks
19                }
20                // Update last to the maximum of current position or last + mi
21                last = std::max((long long) position, last + mi);
22            }
23            return true; // All positions are valid for the given 'mi'
24        };
25
26        // Initialize binary search boundaries
27        int left = 0;
28        int right = start.back() + d - start[0];
29
30        // Perform binary search to find the maximum feasible score
31        while (left < right) {
32            int mid = left + (right - left + 1) / 2; // Calculate mid point
33            if (isFeasible(mid)) {
34                left = mid; // If feasible, move left boundary up
35            } else {
36                right = mid - 1; // If not feasible, move right boundary down
37            }
38        }
39        return left; // Return the maximum possible score
40    }
41};
42

1function maxPossibleScore(start: number[], d: number): number {
2    // Sort the starting points array in ascending order
3    start.sort((a, b) => a - b);
4  
5    // Initialize left and right boundaries for binary search
6    let [l, r] = [0, start.at(-1)! + d - start[0]];
7
8    // Helper function to check if a given mid value is feasible
9    const check = (mi: number): boolean => {
10        // Initialize the last used point in the sequence
11        let last = -Infinity;
12
13        // Iterate over each starting point
14        for (const st of start) {
15            // Check if the current point plus d is less than or equal to last used point plus mid
16            if (last + mi > st + d) {
17                return false; // If not, return false as the mid value is not feasible
18            }
19
20            // Update the last used point to the maximum of current point or last + mi
21            last = Math.max(st, last + mi);
22        }
23
24        return true; // Return true if all points satisfy the condition
25    };
26
27    // Perform binary search to find the maximum possible score
28    while (l < r) {
29        // Calculate mid value
30        const mid = l + ((r - l + 1) >> 1);
31
32        // Use the helper function to check feasibility of mid
33        if (check(mid)) {
34            l = mid; // If feasible, move left boundary to mid
35        } else {
36            r = mid - 1; // Otherwise, adjust the right boundary
37        }
38    }
39
40    // Return the maximum possible score found
41    return l;
42}
43

Time and Space Complexity

The code involves a binary search algorithm applied over a sorted array. Specifically:

Binary Search: The search range spans from 0 to start[-1] + d - start[0]. This range can be considered proportional to the maximum feasible distance, M, across the start array.
Check Function: For each mid value during the binary search, the code iterates over the start list, which has n elements.

Therefore, the time complexity is O(n \times \log M), where n is the length of the start array, and M is the calculated maximum possible value derived from the input bounds (i.e., start[-1] + d - start[0]).

The space complexity, considering only the variables used and no additional data structures apart from the input, remains O(1), as the algorithm primarily manipulates a few integer variables and does not utilize extra space that scales with input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers