436. 寻找右区间--LeetCode_二分

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-right-interval
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目大意是这样的
	数组中的元素由一个区间组成(包含一个左端点和右端点),左端点一定是唯一的
	找到每个元素的右区间
	举个例子
		假设区间A为[1,2],那么区间A的右区间最好就是[2,3]
		也就是说区间A右区间的左端点是大于等于区间A右端点的最小数

二分思路


从暴力算法上看,开销最大的部分就是枚举右区间
如果事先记录数组intervals的左端点并排序,那么右区间就可以二分(有序就可以二分)

代码如下


class Solution {
public:
    vector findRightInterval(vector>& intervals) {
        vector res;

        // intervals的长度为1时要做特判
        if(intervals.size()==1){
            res.push_back(-1);
            return res;
        }
        // 记录intervals中每个区间的左端点和该端点在哪个区间
        vector> tmp;

        for(int i=0;i=intervals[i][1])r=mid;
                else l=mid+1;
            }
            // 如果找到的左端点小于区间i的右端点就记录左端点所在区间
            // 否则记为-1 表示区间i没有右区间
            if(tmp[l].first>=intervals[i][1])res.push_back(tmp[l].second);
            else res.push_back(-1);
        }

        return res;
    }
};

原文链接:,转发请注明来源!