LeetCode436：寻找右区间

题目链接：436. 寻找右区间 - 力扣（LeetCode）

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<pair<int, int>> startIntervals;
        
        int n = intervals.size();

        for(int i = 0; i < n; i++)
        {
            startIntervals.emplace_back(intervals[i][0], i);
        }

        sort(startIntervals.begin(), startIntervals.end());
        vector<int> ans(n, -1);
        
        for(int i = 0; i < n; i++)
        {
            auto it = lower_bound(startIntervals.begin(), startIntervals.end(), make_pair(intervals[i][1], 0));
            if(it != startIntervals.end())
            {
                ans[i] = it->second;
            }
        }
        return ans;
    }
};

题目语言解释：这个题目实际上就是排序加上二分，而lower_bound()的复杂的已经是达到logn，所以就可以使用这个函数，（在这里解释一下这个函数，lower_bound()是找到某个数组的第一个出现的大于等于给定的数）。

代码解释：这个题目首先定义一个vector里面嵌套的一个pair数组，然后去存下来，这个语句很关键。

 startIntervals.emplace_back(intervals[i][0], i);

这个代码顾名思义也就是遍历当前的数和增加i的值，然后去存到这个数组里面。排序。

在定义一个数组，这个数组最关键的是把所有的值赋值为-1，-1因为是题目要求没找到的时候。

然后在去遍历数组的数，找到第一个出现的大于等于这个给定的数。这里有个代码很关键

auto it = lower_bound(startIntervals.begin(), startIntervals.end(), make_pair(intervals[i][1], 0));

make_pair(intervals[i][1], 0)也就是创建一个键值对数组为<intervals[i][1], 0>

这个意思也就是在startIntervals数组里面寻找键值对<intervals[i][1], 0>这个值。

如果找到的话，那就让it指向的pair<int, int>里面的第二个数赋值给ans里面。