How do you maximize the score in Maximize Score of Numbers in Ranges?

To maximize the score, use binary search over the possible scores. For each candidate score, validate it by trying to select integers from the given intervals using a greedy approach.

What is the time complexity of the Maximize Score of Numbers in Ranges problem?

The time complexity is O(n log n log(maxDifference)), where n is the number of intervals and maxDifference is the range between the smallest and largest possible score values.

What pattern is primarily used in solving the Maximize Score of Numbers in Ranges problem?

The main pattern used is binary search over the valid answer space, combined with a greedy approach for validating candidate scores.

How does sorting affect the solution to Maximize Score of Numbers in Ranges?

Sorting the intervals helps in efficiently selecting integers from them by ensuring the greedy approach works optimally, as it allows quick traversal and decision-making for each interval.

What are common pitfalls when solving the Maximize Score of Numbers in Ranges?

Common pitfalls include failing to apply binary search correctly, making mistakes in the validation logic for feasible scores, and neglecting the importance of sorting the intervals.

#3281

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

范围内整数的最大得分

给你一个整数数组 start 和一个整数 d ，代表 n 个区间 [start[i], start[i] + d] 。你需要选择 n 个整数，其中第 i 个整数必须属于第 i 个区间。所选整数的得分定义为所选整数两两之间的最小绝对差。返回所选整数的最大可能得分。示例 1：输入： …

数组二分查找贪心排序

题目描述

给你一个整数数组 start 和一个整数 d，代表 n 个区间 [start[i], start[i] + d]。

你需要选择 n 个整数，其中第 i 个整数必须属于第 i 个区间。所选整数的得分定义为所选整数两两之间的最小绝对差。

返回所选整数的 最大可能得分 。

示例 1：

输入： start = [6,0,3], d = 2

输出： 4

解释：

可以选择整数 8, 0 和 4 获得最大可能得分，得分为 min(|8 - 0|, |8 - 4|, |0 - 4|)，等于 4。

示例 2：

输入： start = [2,6,13,13], d = 5

输出： 5

解释：

可以选择整数 2, 7, 13 和 18 获得最大可能得分，得分为 min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|)，等于 5。

提示：

2 <= start.length <= 10⁵
0 <= start[i] <= 10⁹
0 <= d <= 10⁹

lightbulb

解题思路

方法一：排序 + 二分查找

我们不妨先对 $\textit{start}$ 数组进行排序，然后我们考虑从左到右选择整数，那么得分就等于我们选择的相邻两个整数的差值的最小值。

如果一个差值 $x$ 满足条件，那么对于任意 $x' \lt x$ ，也一定满足条件。因此我们可以使用二分查找的方法来找到最大的满足条件的差值。

我们定义二分查找的左边界 $l = 0$ ，右边界 $r = \textit{start}[-1] + d - \textit{start}[0]$ ，然后我们每次取中间值 $mid = \left\lfloor \frac{l + r + 1}{2} \right\rfloor$ ，然后判断是否满足条件。

我们定义一个函数 $\text{check}(mi)$ 来判断是否满足条件，具体实现如下：

我们定义一个变量 $\textit{last} = -\infty$ ，表示上一个选择的整数。
我们遍历 $\textit{start}$ 数组，如果 $\textit{last} + \textit{mi} > \textit{st} + d$ ，那么说明我们无法选择整数 $\textit{st}$ ，返回 $\text{false}$ 。否则，我们更新 $\textit{last} = \max(\textit{st}, \textit{last} + \textit{mi})$ 。
如果遍历完整个 $\textit{start}$ 数组都满足条件，那么返回 $\text{true}$ 。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 和 $M$ 分别是 $\textit{start}$ 数组的长度和最大值。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands binary search and can apply it in unusual contexts.
question_mark
Candidate can break down complex problems into manageable parts with clear strategies.
question_mark
Candidate demonstrates proficiency with greedy algorithms and interval-based problems.

warning

常见陷阱

外企场景

error
Failure to recognize the binary search over possible scores as the most efficient approach.
error
Improper validation logic when checking if a score is feasible, leading to incorrect answers.
error
Ignoring sorting as a key step for efficiently handling the interval selections.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increasing the number of intervals or the size of d to test scalability.
arrow_right_alt
Introducing constraints where the ranges are no longer uniformly spaced or have overlaps.
arrow_right_alt
Modifying the score condition to include other factors such as maximum instead of minimum differences.

help

常见问题

外企场景

继续练习

#3413 收集连续 K 个袋子可以获得的最多硬币数量 #3534 针对图的路径存在性查询 II #2967 使数组成为等数数组的最小代价