maximize-score-of-numbers-in-ranges

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array of integers <code>start</code> and an integer <code>d</code>, representing <code>n</code> intervals <code>[start[i], start[i] + d]</code>.

You are asked to choose <code>n</code> integers where the <code>ith</code> integer must belong to the <code>ith</code> 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.

&nbsp;
Example 1:

<div class="example-block">
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 <code>min(|8 - 0|, |8 - 4|, |0 - 4|)</code> which equals 4.
</div>

Example 2:

<div class="example-block">
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 <code>min(|2 - 7|, |2 - 13|, |2 - 18|, |7 - 13|, |7 - 18|, |13 - 18|)</code> which equals 5.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= start.length &lt;= 105</code></li>
	<li><code>0 &lt;= start[i] &lt;= 109</code></li>
	<li><code>0 &lt;= d &lt;= 109</code></li>
</ul>

maxPossibleScore

Maximize Score of Numbers in Ranges

Find K-th Smallest Pair Distance

find-k-th-smallest-pair-distance

找出第 K 小的数对距离

Greedy

Array

Binary Search

Sorting

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

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

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

&nbsp;

示例 1：

<div class="example-block">
输入： start = [6,0,3], d = 2

输出： 4

解释：

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

示例 2：

<div class="example-block">
输入： start = [2,6,13,13], d = 5

输出： 5

解释：

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

&nbsp;

提示：

<ul>
	<li><code>2 &lt;= start.length &lt;= 105</code></li>
	<li><code>0 &lt;= start[i] &lt;= 109</code></li>
	<li><code>0 &lt;= d &lt;= 109</code></li>
</ul>