題目： LeetCode - 436. Find Right Interval

題目說明

給一堆區間，求每個區間的最近右邊區間的索引號 ( 右邊區間的 start >= 左邊區間的 end)，若不存在則為 -1。

解題思路

使用 map 紀錄每個區間的起始點及索引號，接著遍歷所有區間，使用 lower_bound() 實現二分查找。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        vector<int> v;
        map<int, int> m;
        auto iter = m.begin();
        for(int i = 0; i < intervals.size(); ++i) m[intervals[i][0]] = i;
        for(auto& interval : intervals)
            v.emplace_back((iter = m.lower_bound(interval[1])) != m.end() ? iter->second : -1);
        return v;
    }
};