Description

给定\(n\)个区间\([lo_i, hi_i]\)，每个区间的\(lo_i\)互不重复，求每一个区间的右侧区间下标。某区间\(i\)的右侧区间\(j\)指的是\(lo_j \ge hi_i\)且\(lo_j\)是所有可选答案中最小的那位

Constraints

时间复杂度不超过\(O(nlogn)\)

Solution

不知道要说什么，总之排序就对了

Code

class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        using Ret = std::tuple<int, int, int>;
        auto &inv = intervals;
        multiset<Ret> ms;
        for(size_t i = 0; i < inv.size(); ++i) {
            ms.emplace(inv[i][0], inv[i][1], i);
        }
        vector<int> ans;
        size_t index {0};
        using Ref = std::reference_wrapper<size_t>;
        struct guard: Ref {
            using Ref::Ref;
            ~guard() {(*this)++;} 
        };
        for(auto &i : inv) {
            guard g(index);
            if(i[0] == i[1]) {
                ans.push_back(index);
                continue;
            }
            auto iter = ms.lower_bound(make_tuple(i[0], i[1], 0));
            auto val = *iter;
            ms.erase(iter);
            iter = ms.lower_bound(make_tuple(i[1], i[1], 0));
            if(iter == ms.end()) ans.emplace_back(-1);
            else ans.emplace_back(get<2>(*iter));
            ms.insert(move(val));
        }
        return ans;
    }
};

Link

LeetCode-436 Find Right Interval