刷题-leetcode：436. 寻找右区间

题目地址：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