436.寻找右区间

链接：436.寻找右区间
难度：Medium
标签：数组、二分查找、排序
简介：返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

题解 1 - cpp

• 编辑时间：2022-05-20
• 执行用时：60ms
• 内存消耗：23.3MB
• 编程语言：cpp
• 解法介绍：bs。

class Solution {
   public:
    vector<int> findRightInterval(vector<vector<int>> &intervals) {
        int n = intervals.size();
        vector<int> ans(n, -1);
        vector<int> list(n);
        for (int i = 0; i < n; i++) list[i] = i;
        sort(list.begin(), list.end(), [&](int &a, int &b) -> bool {
            if (intervals[a][0] == intervals[b][0])
                return intervals[a][1] < intervals[b][1];
            return intervals[a][0] < intervals[b][0];
        });
        for (int i = 0; i < n; i++)
            ans[i] = bs(intervals, list, intervals[i][1]);
        return ans;
    }
    int bs(vector<vector<int>> &intervals, vector<int> &list, int num) {
        int l = 0, r = intervals.size(), m;
        while (l < r) {
            m = (l + r) >> 1;
            if (intervals[list[m]][0] >= num)
                r = m;
            else
                l = m + 1;
        }
        if (r == intervals.size()) return -1;
        return list[l];
    }
};