find-right-interval

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 <code>intervals</code>, where <code>intervals[i] = [starti, endi]</code> and each <code>starti</code> is unique.

The right interval for an interval <code>i</code> is an interval <code>j</code> such that <code>startj &gt;= endi</code> and <code>startj</code> is minimized. Note that <code>i</code> may equal <code>j</code>.

Return an array of right interval indices for each interval <code>i</code>. If no right interval exists for interval <code>i</code>, then put <code>-1</code> at index <code>i</code>.

&nbsp;
Example 1:

<pre>
Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.
</pre>

Example 2:

<pre>
Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is &gt;= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is &gt;= end2 = 2.
</pre>

Example 3:

<pre>
Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is &gt;= end1 = 3.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 2 * 104</code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>-106 &lt;= starti &lt;= endi &lt;= 106</code></li>
	<li>The start point of each interval is unique.</li>
</ul>

findRightInterval

Find Right Interval

Data Stream as Disjoint Intervals

data-stream-as-disjoint-intervals

将数据流变为多个不相交区间

Array

Binary Search

Sorting

给你一个区间数组 <code>intervals</code> ，其中&nbsp;<code>intervals[i] = [starti, endi]</code> ，且每个&nbsp;<code>starti</code> 都 不同 。

区间 <code>i</code> 的 右侧区间&nbsp;是满足 <code>startj&nbsp;&gt;= endi</code>，且 <code>startj</code> 最小&nbsp;的区间 <code>j</code>。注意 <code>i</code> 可能等于 <code>j</code> 。

返回一个由每个区间 <code>i</code>&nbsp;对应的 右侧区间 下标组成的数组。如果某个区间 <code>i</code> 不存在对应的 右侧区间 ，则下标 <code>i</code> 处的值设为 <code>-1</code> 。
&nbsp;

示例 1：

<pre>
输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。
</pre>

示例 2：

<pre>
输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。
</pre>

示例 3：

<pre>
输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1,2,-1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;=&nbsp;intervals.length &lt;= 2 * 104</code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>-106 &lt;= starti &lt;= endi &lt;= 106</code></li>
	<li>每个间隔的起点都 不相同</li>
</ul>