436. 尋找右區間–LeetCode_二分

• 2022 年 8 月 19 日
• 筆記
• 二分演算法, 演算法

來源：力扣（LeetCode）
鏈接：//leetcode.cn/problems/find-right-interval
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

題目大意是這樣的
	數組中的元素由一個區間組成(包含一個左端點和右端點),左端點一定是唯一的
	找到每個元素的右區間
	舉個例子
		假設區間A為[1,2],那麼區間A的右區間最好就是[2,3]
		也就是說區間A右區間的左端點是大於等於區間A右端點的最小數

二分思路

從暴力演算法上看，開銷最大的部分就是枚舉右區間
如果事先記錄數組intervals的左端點並排序，那麼右區間就可以二分(有序就可以二分)

程式碼如下

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

        // intervals的長度為1時要做特判
        if(intervals.size()==1){
            res.push_back(-1);
            return res;
        }
        // 記錄intervals中每個區間的左端點和該端點在哪個區間
        vector<pair<int,int>> tmp;

        for(int i=0;i<intervals.size();i++)
            tmp.push_back({intervals[i][0],i});
        // 將這些端點排序
        sort(tmp.begin(),tmp.end());
        for(int i=0;i<intervals.size();i++){
            int l=0,r=tmp.size()-1,mid;
            // 二分尋找對應的左端點
            while(l<r){
                mid = (l+r)/2;
                if(tmp[mid].first>=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;
    }
};