C++ map solution


  • 24
    H
    class Solution {
    public:
        vector<int> findRightInterval(vector<Interval>& intervals) {
            map<int, int> hash;
            vector<int> res;
            int n = intervals.size();
            for (int i = 0; i < n; ++i)
                hash[intervals[i].start] = i;
            for (auto in : intervals) {
                auto itr = hash.lower_bound(in.end);
                if (itr == hash.end()) res.push_back(-1);
                else res.push_back(itr->second);
            }
            return res;
        }
    };
    

  • 2
    T

    @Hanafubuki Great solution. But the name of map "hash" is misleading somehow. Since map is usually implemented by RBT not hashing table.


  • 0

    Elegant Solution!


  • 0
    M

    To leetcode:
    This is ridiculous, std::map::lower_bound is 50 times faster than the std::lower_bound on a sorted array.
    Besides that, in so many other problems, the code written in plain C is running much faster than C++, it seems Leetcode doesn't compile the submitted code with any optimizing option.
    My point is that, the problems on your website should lead people to learn programming in the correct direction, not misguiding them.


Log in to reply
 

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