This type of questions are also asked in coding interviews.
**Concept Brute Force: **
O(n^2)
very simple you just need to traverse the given vector two times and for each i you can calculate the result and store it.
but as this gives TLE.
So what can we do.
O(nlogn)
efficient
It will be easier to solve if we can deduce it into a search on sorted lists.
so here we just store first value of all the indexes and also the indexes in a pair.
and then after sorting do a binary search.
and it solves.
class Solution {
public:
// 1->0 , 2->1, 3->2
//
int bsearch(vector<pair<int,int>> &temp,int val){
int n = temp.size();
if(val > temp[n-1].first) return -1;
int f=0,l = n-1;
int mid;
int ans;
while(f <= l){
mid = (f+l)/2;
if(temp[mid].first >= val){
ans = temp[mid].second;
l = mid-1;
}else{
f = mid + 1;
}
}
return ans;
}
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> answer(n,-1);
vector<pair<int,int>> temp(n);
for(int i=0;i<n;++i)
{
temp[i] = make_pair(intervals[i][0],i);
}
sort(temp.begin(),temp.end());
// now i can do binary search on this
for(int i=0;i<n;++i){
answer[i] = bsearch(temp,intervals[i][1]);
}
return answer;
}
};Comments (0)