Formatted question description: https://leetcode.ca/all/436.html

# 436. Find Right Interval (Medium)

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.

For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

1. You may assume the interval's end point is always bigger than its start point.
2. You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.


Example 2:

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.


Example 3:

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.


NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Related Topics:
Binary Search

Similar Questions:

// OJ: https://leetcode.com/problems/find-right-interval/

// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& A) {
int N = A.size();
vector<int> id(N), ans;
iota(begin(id), end(id), 0);
sort(begin(id), end(id), [&](int a, int b) { return A[a] < A[b]; });
for (auto &i : A) {
auto j = lower_bound(begin(id), end(id), i, [&](int idx, int val) { return A[idx] < val; });
ans.push_back(j == end(id) ? -1 : *j);
}
return ans;
}
};


Or manually write the binary search.

// OJ: https://leetcode.com/problems/find-right-interval/

// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& A) {
int N = A.size();
vector<int> id(N), ans;
iota(begin(id), end(id), 0);
sort(begin(id), end(id), [&](int a, int b) { return A[a] < A[b]; });
for (auto &i : A) {
int L = 0, R = N - 1;
while (L <= R) {
int M = (L + R) / 2;
if (A[id[M]] < i) L = M + 1;
else R = M - 1;
}
ans.push_back(L == N ? -1 : id[L]);
}
return ans;
}
};


Java

class Solution {
public int[] findRightInterval(int[][] intervals) {
int length = intervals.length;
int[][] intervalsIndices = new int[length];
for (int i = 0; i < length; i++) {
intervalsIndices[i] = intervals[i];
intervalsIndices[i] = intervals[i];
intervalsIndices[i] = i;
}
Arrays.sort(intervalsIndices, new Comparator<int[]>() {
public int compare(int[] intervalIndex1, int[] intervalIndex2) {
if (intervalIndex1 != intervalIndex2)
return intervalIndex1 - intervalIndex2;
else
return intervalIndex1 - intervalIndex2;
}
});
int[][] rightIntervalsIndices = new int[length];
for (int i = 0; i < length; i++) {
rightIntervalsIndices[i] = -1;
int curIntervalEnd = intervalsIndices[i];
for (int j = i + 1; j < length; j++) {
int nextIntervalStart = intervalsIndices[j];
if (nextIntervalStart >= curIntervalEnd) {
rightIntervalsIndices[i] = intervalsIndices[j];
break;
}
}
rightIntervalsIndices[i] = intervalsIndices[i];
}
Arrays.sort(rightIntervalsIndices, new Comparator<int[]>() {
public int compare(int[] intervalIndex1, int[] intervalIndex2) {
return intervalIndex1 - intervalIndex2;
}
});
int[] rightIntervals = new int[length];
for (int i = 0; i < length; i++)
rightIntervals[i] = rightIntervalsIndices[i];
return rightIntervals;
}
}