smallest-range-covering-elements-from-k-lists

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 have <code>k</code> lists of sorted integers in non-decreasing&nbsp;order. Find the smallest range that includes at least one number from each of the <code>k</code> lists.

We define the range <code>[a, b]</code> is smaller than range <code>[c, d]</code> if <code>b - a &lt; d - c</code> or <code>a &lt; c</code> if <code>b - a == d - c</code>.

&nbsp;
Example 1:

<pre>
Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].
</pre>

Example 2:

<pre>
Input: nums = [[1,2,3],[1,2,3],[1,2,3]]
Output: [1,1]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>nums.length == k</code></li>
	<li><code>1 &lt;= k &lt;= 3500</code></li>
	<li><code>1 &lt;= nums[i].length &lt;= 50</code></li>
	<li><code>-105 &lt;= nums[i][j] &lt;= 105</code></li>
	<li><code>nums[i]</code>&nbsp;is sorted in non-decreasing order.</li>
</ul>

smallestRange

Smallest Range Covering Elements from K Lists

Minimum Window Substring

minimum-window-substring

最小覆盖子串

Greedy

Array

Hash Table

Sorting

Sliding Window

Heap (Priority Queue)

你有&nbsp;<code>k</code>&nbsp;个 非递减排列 的整数列表。找到一个 最小 区间，使得&nbsp;<code>k</code>&nbsp;个列表中的每个列表至少有一个数包含在其中。

我们定义如果&nbsp;<code>b-a &lt; d-c</code>&nbsp;或者在&nbsp;<code>b-a == d-c</code>&nbsp;时&nbsp;<code>a &lt; c</code>，则区间 <code>[a,b]</code> 比 <code>[c,d]</code> 小。

&nbsp;

示例 1：

<pre>
输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
</pre>

示例 2：

<pre>
输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]
</pre>

&nbsp;

提示：

<ul>
	<li><code>nums.length == k</code></li>
	<li><code>1 &lt;= k &lt;= 3500</code></li>
	<li><code>1 &lt;= nums[i].length &lt;= 50</code></li>
	<li><code>-105 &lt;= nums[i][j] &lt;= 105</code></li>
	<li><code>nums[i]</code> 按非递减顺序排列</li>
</ul>

&nbsp;