Concise O(nlgn) C++ solution using BST(std::map)


  • 3
    A

    std::map's implementation is red-black-tree, lower_bound finds the first key in the BST that is no less than the given key. We first store all the indexes of intervals using starting point as key into the BST, then search it using end points of each interval. Time complexity O(nlgn).

    class Solution {
    public:
        vector<int> findRightInterval(vector<Interval>& intervals) {
            std::map<int,int> start_indexes;
            for (int index = 0; index < intervals.size(); ++index) {
            	start_indexes.emplace(intervals[index].start, index);
            }
            vector<int> result;
            for (auto& interval : intervals) {
            	auto lower_bound_it = start_indexes.lower_bound(interval.end);
            	result.push_back(lower_bound_it == start_indexes.end() ? -1 : lower_bound_it->second);
            }
            return result;
        }
    };
    

Log in to reply
 

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