# LeetCode Find Right Interval

LeetCode Find Right Interval

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.```

```typedef struct MyInterval {
Interval inter;
int idx;
MyInterval(Interval inter_, int idx_) :inter(inter_), idx(idx_) {};
bool operator<(const MyInterval& myi) const{
return this->inter.start < myi.inter.start; // 所有start不相同
}
};

class Solution2 {
public:
vector<int> findRightInterval(vector<Interval>& intervals) {
int n = intervals.size();
vector<MyInterval> myvs;
for (int i = 0; i < n; ++i) {
MyInterval myint(intervals[i], i);
myvs.push_back(myint);
}
sort(myvs.begin(), myvs.end());
vector<int> ans(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) { // 线性查找
if (myvs[j].inter.start >= myvs[i].inter.end) {
ans[myvs[i].idx] = myvs[j].idx;
break;
}
}
}
return ans;
}
};
```

```class Solution {
private:
int binsearch(const vector<int>& starts, int target) {
int l = 0, r = starts.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (starts[m] == target)return starts[m];
if (starts[m] < target)l = m + 1;
else r = m - 1;
}
return starts[l];
}
public:
vector<int> findRightInterval(vector<Interval>& intervals) {
int n = intervals.size();
vector<int> starts;
unordered_map<int, int> hash;
for (int i = 0; i < n; ++i) {
starts.push_back(intervals[i].start);
hash[intervals[i].start] = i;
}
sort(starts.begin(), starts.end());
vector<int> ans(n, -1);
for (int i = 0; i < n; ++i) {
if (intervals[i].end <= starts[n - 1]) {
int t = binsearch(starts, intervals[i].end);
ans[i] = hash[t];
}
}
return ans;
}
};
```