365天挑战LeetCode1000题——Day 012 每日一题

• 前言
• 1. [寻找右区间](https://leetcode.cn/problems/find-right-interval/)
• • 1.1 二分查找
• 总结

今天还是一题，但是重新学习了快排，堆排以及第K小数，写在另外一个文档里面……

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。

区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。

返回一个由每个区间 i 的 右侧区间 在 intervals 中对应下标组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

这题用暴力会寄。
利用C++提供的lower_bound()进行二分查找，先将所有的左区间与下标组成的pair加入一个vector中，然后进行排序，然后对每个右区间调用lower_bound()。

class Solution {
public:
    vector findRightInterval(vector>& intervals) {
        int n = intervals.size();
        vector> startIntervals;
        for (int i = 0; i < n; i++) {
            startIntervals.emplace_back(intervals[i][0], i);
        }
        sort(startIntervals.begin(), startIntervals.end());

        vector 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;
    }
};

今天把操作系统实验检查完了，还是比较开心的，当然感觉和班上的大佬还有差距啊，继续加油吧！