Array
Binary Search
Sorting
Description
You are given an array of intervals
, where intervals[i] = [starti , endi ]
and each starti
is unique .
The right interval for an interval i
is an interval j
such that startj >= endi
and startj
is minimized . Note that i
may equal j
.
Return an array of right interval indices for each interval i
. If no right interval exists for interval i
, then put -1
at index i
.
Example 1:
Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.
Example 2:
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 >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.
Example 3:
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 >= end1 = 3.
Constraints:
1 <= intervals.length <= 2 * 104
intervals[i].length == 2
-106 <= starti <= endi <= 106
The start point of each interval is unique .
Solutions
Solution 1
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def findRightInterval ( self , intervals : List [ List [ int ]]) -> List [ int ]:
for i , v in enumerate ( intervals ):
v . append ( i )
intervals . sort ()
n = len ( intervals )
ans = [ - 1 ] * n
for _ , e , i in intervals :
j = bisect_left ( intervals , [ e ])
if j < n :
ans [ i ] = intervals [ j ][ 2 ]
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 class Solution {
public int [] findRightInterval ( int [][] intervals ) {
int n = intervals . length ;
List < int []> starts = new ArrayList <> ();
for ( int i = 0 ; i < n ; ++ i ) {
starts . add ( new int [] { intervals [ i ][ 0 ] , i });
}
starts . sort ( Comparator . comparingInt ( a -> a [ 0 ] ));
int [] res = new int [ n ] ;
int i = 0 ;
for ( int [] interval : intervals ) {
int left = 0 , right = n - 1 ;
int end = interval [ 1 ] ;
while ( left < right ) {
int mid = ( left + right ) >> 1 ;
if ( starts . get ( mid ) [ 0 ] >= end ) {
right = mid ;
} else {
left = mid + 1 ;
}
}
res [ i ++] = starts . get ( left ) [ 0 ] < end ? - 1 : starts . get ( left ) [ 1 ] ;
}
return res ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public :
vector < int > findRightInterval ( vector < vector < int >>& intervals ) {
int n = intervals . size ();
vector < pair < int , int >> starts ;
for ( int i = 0 ; i < n ; ++ i ) {
starts . emplace_back ( make_pair ( intervals [ i ][ 0 ], i ));
}
sort ( starts . begin (), starts . end ());
vector < int > res ;
for ( auto interval : intervals ) {
int left = 0 , right = n - 1 ;
int end = interval [ 1 ];
while ( left < right ) {
int mid = left + right >> 1 ;
if ( starts [ mid ]. first >= end )
right = mid ;
else
left = mid + 1 ;
}
res . push_back ( starts [ left ]. first < end ? -1 : starts [ left ]. second );
}
return res ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 func findRightInterval ( intervals [][] int ) [] int {
n := len ( intervals )
starts := make ([][] int , n )
for i := 0 ; i < n ; i ++ {
starts [ i ] = make ([] int , 2 )
starts [ i ][ 0 ] = intervals [ i ][ 0 ]
starts [ i ][ 1 ] = i
}
sort . Slice ( starts , func ( i , j int ) bool {
return starts [ i ][ 0 ] < starts [ j ][ 0 ]
})
var res [] int
for _ , interval := range intervals {
left , right , end := 0 , n - 1 , interval [ 1 ]
for left < right {
mid := ( left + right ) >> 1
if starts [ mid ][ 0 ] >= end {
right = mid
} else {
left = mid + 1
}
}
val := - 1
if starts [ left ][ 0 ] >= end {
val = starts [ left ][ 1 ]
}
res = append ( res , val )
}
return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 function findRightInterval ( intervals : number [][]) : number [] {
const n = intervals . length ;
const starts = Array . from ({ length : n }). map (() => new Array < number > ( 2 ));
for ( let i = 0 ; i < n ; i ++ ) {
starts [ i ][ 0 ] = intervals [ i ][ 0 ];
starts [ i ][ 1 ] = i ;
}
starts . sort (( a , b ) => a [ 0 ] - b [ 0 ]);
return intervals . map (([ _ , target ]) => {
let left = 0 ;
let right = n ;
while ( left < right ) {
const mid = ( left + right ) >>> 1 ;
if ( starts [ mid ][ 0 ] < target ) {
left = mid + 1 ;
} else {
right = mid ;
}
}
if ( left >= n ) {
return - 1 ;
}
return starts [ left ][ 1 ];
});
}
GitHub