# Leetcode 436 Solution

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

## Solution

``````/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
int FindFirstNotLessThan(const vector<pair<int, int>>& a, int target)
{
int l = 0;
int r = a.size() - 1;

while (l <= r)
{
int m = (l + r) / 2;

if (a[m].first >= target)
r = m - 1;
else
l = m + 1;
}

if (l < a.size())
return a[l].second;
else
return -1;
}

vector<int> findRightInterval(vector<Interval>& intervals) {
vector<pair<int, int>> a(intervals.size());
vector<int> res(intervals.size());

for (int i = 0; i < intervals.size(); i++)
{
a[i].first = intervals[i].start;
a[i].second = i;
}

sort(a.begin(), a.end(),  [] (const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.first < rhs.first;});

for (int i = 0; i < intervals.size(); i++)
{
res[i] = FindFirstNotLessThan(a, intervals[i].end);
}

return res;
}
};
``````