minimum-interval-to-include-each-query

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 a 2D integer array <code>intervals</code>, where <code>intervals[i] = [lefti, righti]</code> describes the <code>ith</code> interval starting at <code>lefti</code> and ending at <code>righti</code> (inclusive). The size of an interval is defined as the number of integers it contains, or more formally <code>righti - lefti + 1</code>.

You are also given an integer array <code>queries</code>. The answer to the <code>jth</code> query is the size of the smallest interval <code>i</code> such that <code>lefti &lt;= queries[j] &lt;= righti</code>. If no such interval exists, the answer is <code>-1</code>.

Return an array containing the answers to the queries.

&nbsp;
Example 1:

<pre>
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.
</pre>

Example 2:

<pre>
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>1 &lt;= lefti &lt;= righti &lt;= 107</code></li>
	<li><code>1 &lt;= queries[j] &lt;= 107</code></li>
</ul>

minInterval

Minimum Interval to Include Each Query

Number of Flowers in Full Bloom

number-of-flowers-in-full-bloom

花期内花的数目

Array

Binary Search

Sorting

Line Sweep

Heap (Priority Queue)

给你一个二维整数数组 <code>intervals</code> ，其中 <code>intervals[i] = [lefti, righti]</code> 表示第 <code>i</code> 个区间开始于 <code>lefti</code> 、结束于 <code>righti</code>（包含两侧取值，闭区间）。区间的 长度 定义为区间中包含的整数数目，更正式地表达是 <code>righti - lefti + 1</code> 。

再给你一个整数数组 <code>queries</code> 。第 <code>j</code> 个查询的答案是满足&nbsp;<code>lefti &lt;= queries[j] &lt;= righti</code> 的 长度最小区间 <code>i</code> 的长度 。如果不存在这样的区间，那么答案是 <code>-1</code> 。

以数组形式返回对应查询的所有答案。

&nbsp;

示例 1：

<pre>
输入：intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
输出：[3,3,1,4]
解释：查询处理如下：
- Query = 2 ：区间 [2,4] 是包含 2 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 3 ：区间 [2,4] 是包含 3 的最小区间，答案为 4 - 2 + 1 = 3 。
- Query = 4 ：区间 [4,4] 是包含 4 的最小区间，答案为 4 - 4 + 1 = 1 。
- Query = 5 ：区间 [3,6] 是包含 5 的最小区间，答案为 6 - 3 + 1 = 4 。
</pre>

示例 2：

<pre>
输入：intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
输出：[2,-1,4,6]
解释：查询处理如下：
- Query = 2 ：区间 [2,3] 是包含 2 的最小区间，答案为 3 - 2 + 1 = 2 。
- Query = 19：不存在包含 19 的区间，答案为 -1 。
- Query = 5 ：区间 [2,5] 是包含 5 的最小区间，答案为 5 - 2 + 1 = 4 。
- Query = 22：区间 [20,25] 是包含 22 的最小区间，答案为 25 - 20 + 1 = 6 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 105</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>1 &lt;= lefti &lt;= righti &lt;= 107</code></li>
	<li><code>1 &lt;= queries[j] &lt;= 107</code></li>
</ul>