C++ Two sorted vectors O(nlogn) solution


  • 0
    A

    No tree, no hash, no binary search, just two sorted vectors (excluding the output vector).

    15 / 15 test cases passed
    Status: Accepted
    Runtime: 116 ms

    class Solution {
    public:
        vector<int> findRightInterval(vector<Interval>& intervals) {
            uint siz = intervals.size(), cur = 0;
            vector<int> res(siz);
            vector<pair<int, uint>> v(siz), u(siz);
            for (uint i = 0; i < siz; i++) {
                v[i] = pair<int, uint>(intervals[i].end, i);
                u[i] = pair<int, uint>(intervals[i].start, i);
            }
            sort(v.begin(), v.end());
            sort(u.begin(), u.end());
            for (auto& p : u) {
                while (v[cur].first <= p.first) res[v[cur++].second] = p.second;
            }
            while (cur < siz) res[v[cur++].second] = -1;
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.