Algorithm
Problem Name: 436. Find Right Interval
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 * 104intervals[i].length == 2-106 <= starti <= endi <= 106- The start point of each interval is unique.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> findRightInterval(vector < Interval>& intervals) {
vector<int>res;
map < int, int>m;
for(int i = 0; i < intervals.size(); i++) m[intervals[i].start] = i;
for(auto i: intervals){
auto p = m.lower_bound(i.end);
res.push_back(p == m.end() ? -1 : (*p).second);
}
return res;
}
};
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] findRightInterval(int[][] intervals) {
TreeMap();
for (int i = 0; i < intervals.length; i++) {
map.computeIfAbsent(intervals[i][0], k -> new PriorityQueue<>(
Comparator.comparingInt(o -> intervals[o][0]))
).add(i);
}
int[] ans = new int[intervals.length];
Arrays.fill(ans, -1);
for (int i = 0; i < intervals.length; i++) {
Integer upper = map.ceilingKey(intervals[i][1]);
if (upper != null) {
ans[i] = map.get(upper).peek();
}
}
return ans;
}
}
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const findRightInterval = function(intervals) {
const res = []
const arrary = intervals
.map((interval, idx) => ({ interval, idx }))
.sort((obj1, obj2) => obj1.interval[0] - obj2.interval[0])
for (let interval of intervals) {
const val = interval[interval.length - 1]
let left = 0,
right = intervals.length
while (left < right) {
const mid = Math.floor((left + right) / 2)
if (arrary[mid].interval[0] >= val) {
right = mid
} else {
left = mid + 1
}
}
if (left >= intervals.length) {
res.push(-1)
} else {
res.push(arrary[left].idx)
}
}
return res
}
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findRightInterval(self, intervals):
def binarySearch(l, r):
x, found = intervals[l - 1].end, None
while l <= r:
mid = (l + r) // 2
if intervals[mid].start >= x:
r = mid - 1
found = mid
else:
l = mid + 1
return ind[intervals[found]] if found != None else -1
root = intervals[:]
ind = {intr:i for i, intr in enumerate(root)}
intervals.sort(key = lambda x: x.start)
for i in range(len(intervals)):
root[ind[intervals[i]]] = binarySearch(i + 1, len(intervals) - 1)
return root
Input
Output
#5 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0436_FindRightInterval
{
public int[] FindRightInterval(int[][] intervals)
{
var startIndex = new SortedDictionary < int, int>();
for (int i = 0; i < intervals.Length; i++)
startIndex[intervals[i][0]] = i;
var results = new int[intervals.Length];
var starts = startIndex.Keys.ToArray();
for (int i = 0; i < intervals.Length; i++)
{
var index = Array.BinarySearch(starts, intervals[i][1]);
if (index < 0)
index = ~index;
results[i] = index == intervals.Length ? -1 : startIndex[starts[index]];
}
return results;
}
}
}
Input
Output