题目：给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都不同 。
区间 i 的右侧区间可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。
返回一个由每个区间 i 的右侧区间在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的右侧区间 ，则下标 i 处的值设为 -1 。
解法：
- 一开始的思路是在最外层遍历每个区间的右端点
intervals[i][1]记为right，里面一层遍历每个区间的左端点intervals[j][0]记为left，如果left>=right，这里要分两种情况：
- 如果right还没有找到右侧区间则直接将left的索引放入容器的对应位置，
- 如果right已经找到右侧区间，此时就需要将这两个left作比较，将最小的left的索引放入容器的对应位置。
时间复杂度是O(n^2)，空间复杂度是O(1)。这种方法运行会超时。
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
vector<int> v;
for (int i = 0; i < intervals.size(); i++)
{
int right = intervals[i][1];
int j = 0;
for (; j < intervals.size(); j++)
{
int left = intervals[j][0];
if (left >= right)
{
if (i != v.size() - 1)
{
v.push_back(j);
}
else
{
if (v.back() > left)
{
v.pop_back();
v.push_back(j);
}
}
}
}
if (i != v.size() - 1)
{
v.push_back(-1);
}
}
return v;
}
};
- 排序+二分查找
首先将每个区间的起始位置和索引放入map中，即{intervals[i][0],i}，map的key值有序，所以无需再进行排序。然后再遍历每个区间的右端点intervals[i][1]，利用二分查找map中大于等于intervals[i][1]中的最小值val(这个查找可以用库函数lower_bound来完成)，此时i对应的右侧区间为val对应的索引。
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> v(n,-1);
map<int,int> m;
for(int i = 0; i < n; i++)
{
m[intervals[i][0]] = i;
}
for(int i = 0; i < n; i++)
{
auto it = m.lower_bound(intervals[i][1]);
if(it != m.end())
{
v[i] = it->second;
}
}
return v;
}
};
时间复杂度为O(nlogn)，其中n为区间数组的长度，logn为二分查找。
空间复杂度为O(n)，map一共存储了n个元素。
lower_bound库函数介绍： lower_bound()、upper_bound()、equal_range() 以及 binary_search() 这 4 个查找函数，它们的底层实现采用的都是二分查找的方式。
lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素，返回的是迭代器。如果是线性容器，如vector和string，则lower_bound(vector.begin(),vector.end(),key)；如果map或者list，则有自己的内置函数直接map.lower_bound(key)。
- 排序+双指针
startmap存储所有区间的起始点并从小到大排序；endmap存储所有区间的终止点并从小到大排序。 我们从endmap数组中取出第i个区间，就可以从左到右扫描startmap数组中的区间起点来找到满足右区间条件的区间。设endmap数组中第i个元素的右区间为startmap数组中的第j个元素，此时可以知道startmap[j?1][0]<endmap[i][1],startmap[j][0]≥endmap[i][1]。当我们遍历endmap数组中第i+1个元素时，我们不需要从第一个索引开始扫描startmap数组，可以直接从第j个元素开始扫描startmap数组。由于数组中所有的元素都是已排序，因此可以知道startmap[j?1][0]<endmap[i][1]≤endmap[i+1][1]，所以数组startmap的前j?1的元素的起始点都小于endmap[i+1][1]，因此可以直接跳过前j?1个元素，只需要从j开始搜索即可。
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> result(n,-1);
vector<pair<int,int>> startmap;
vector<pair<int,int>> endmap;
for(int i = 0; i < intervals.size(); i++)
{
startmap.emplace_back(intervals[i][0],i);
endmap.emplace_back(intervals[i][1],i);
}
sort(startmap.begin(),startmap.end());
sort(endmap.begin(),endmap.end());
for(int i = 0,j = 0; i < n && j < n; i++)
{
while(j < n && endmap[i].first > startmap[j].first)
{
j++;
}
if(j < n)
{
result[endmap[i].second] = startmap[j].second;
}
}
return result;
}
};
时间复杂度为O(nlogn)，n是数组区间长度，两个数组的排序时间为O(nlogn)，查找每个区间的右侧区间的时间复杂度为O(logn)，所以时间复杂度为O(nlogn)。
空间复杂度为O(n)，n为区间数组的长度。
