题目地址：https://leetcode-cn.com/problems/find-right-interval/
给定一组区间，对于每一个区间 i，检查是否存在一个区间 j，它的起始点大于或等于区间 i 的终点，这可以称为 j 在 i 的“右侧”。
对于任何区间，你需要存储的满足条件的区间 j 的最小索引，这意味着区间 j 有最小的起始点可以使其成为“右侧”区间。如果区间 j 不存在，则将区间 i 存储为 -1。最后，你需要输出一个值为存储的区间值的数组。
注意:
你可以假设区间的终点总是大于它的起始点。
你可以假定这些区间都不具有相同的起始点。
示例 1:输入: [ [1,2] ]
输出: [-1]解释:集合中只有一个区间，所以输出-1。
示例 2:输入: [ [3,4], [2,3], [1,2] ]
输出: [-1, 0, 1]解释:对于[3,4]，没有满足条件的“右侧”区间。
对于[2,3]，区间[3,4]具有最小的“右”起点;
对于[1,2]，区间[2,3]具有最小的“右”起点。
示例 3:输入: [ [1,4], [2,3], [3,4] ]
输出: [-1, 2, -1]解释:对于区间[1,4]和[3,4]，没有满足条件的“右侧”区间。
对于[2,3]，区间[3,4]有最小的“右”起点。
编程思路
此题可以硬解，先遍历所有区间尾，对于每尾再遍历一次所有的头，找出最小的即可。我选择麻烦一点，先对区间们依据区间首进行升序排序，然后再从头依次遍历区间尾，从该区间起向后查找。
-
二路归并排序
对区间的排序采用二路归并排序。归并排序使用分治思想，稳定，最好最坏平均时间复杂度都是O(nlog2n)。同样时间复杂度的排序中，快速排序不稳定，且当元素顺序和逆序时出现最坏情况O(n²)，堆排序不稳定。归并排序消耗内存O(n)。
归并排序
下面是归并排序过程，核心就是比较左右指针内容的大小，画画板做的gif将就着看吧。
归并过程.gif -
折半查找
区间排序完成后，起点已经是升序，接下来只需对所有区间尾依次进行处理，在其他区间找出比其大得最少或者值相等的一个起点。我们只需要对其后的区间的头进行查找即可，由于区间起点升序，因此采用二分查找法快些。
例如对{2,5,7,17,18,56}进行折半查找，查找的路径相当于一个平衡的二叉排序树，查找成功也好，失败也好，最多也就比较树高次，是O(log2n)数量级。
image.png
代码
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int size=intervals.size();
vector<int> indexes;
vector<int> results;
for(int k=0;k<size;k++){
indexes.push_back(k);
results.push_back(k);
}
mergeSort(intervals,indexes,0,size-1);
//binary search
for(int k=0;k<size;k++){
int target=intervals[indexes[k]][1];
int low=k+1,high=size-1,mid;
int result=-1;
while(low<=high){
mid=(low+high)/2;
if(target==intervals[indexes[mid]][0]){//found
result=indexes[mid];
break;
}
else if(target<intervals[indexes[mid]][0]){
result=indexes[mid];
high=mid-1;
}
else if(target>intervals[indexes[mid]][0]){
low=mid+1;
}
}
results[indexes[k]]=result;
}
return results;
}
/*
custom merge sort,modified units' index will be stored in inputIndex
*/
void mergeSort(vector<vector<int>>& inputVec,vector<int> &inputIndex,int low,int high){
if(low<high){
int mid=(low+high)/2;
mergeSort(inputVec,inputIndex,low,mid);//left part sort
mergeSort(inputVec,inputIndex,mid+1,high);//right part sort
innerMerge(inputVec,inputIndex,low,mid,high);//both left and right already sorted,now merge them into one piece.
}
}
/*
merge low ~ mid and mid+1 ~ high into one piece
*/
void innerMerge(vector<vector<int>>& inputVec,vector<int> &inputIndex,int low,int mid,int high){
int i,j,k;
auto indexCopy=inputIndex;
printf("%d ",low);
for(i=low,j=mid+1,k=low;i<=mid&&j<=high;k++){//caution:k=low
if(inputVec[indexCopy[i]][0]<inputVec[indexCopy[j]][0]){//left<right
inputIndex[k]=indexCopy[i++];
}
else {//left>right
inputIndex[k]=indexCopy[j++];
}
}
while(i<=mid){
inputIndex[k++]=indexCopy[i++];
}
while(j<=high){
inputIndex[k++]=indexCopy[j++];
}
}
};
性能：
都不好意思贴出来了
image.png
