[715. Range Module] C++ Map AC


  • 0
    class RangeModule {
    public:
    map<int,int> mp;
    RangeModule() {}
    
    void addRange(int left, int right) {
        //upper_bound: Returns an iterator pointing to the first element in the container whose key is considered to go after k.
        //lower_bound: Returns an iterator pointing to the first element in the container whose key is not considered to go before k (i.e., either it is equivalent or goes after).
        auto e = mp.upper_bound(right);//terminal point
        auto s = mp.upper_bound(left - 1);//possible start point
        if(s != mp.begin()) s--;
        while(s != e && s->second < left){
            s++;
        }
        while(s != e){
            auto temp_itr = s;
            left = min(left, temp_itr->first);
            right = max(right, temp_itr->second);
            s++;
            mp.erase(temp_itr);
        }
        mp.insert(e, {left, right});
    }
    
    bool queryRange(int left, int right) {
        auto e = mp.upper_bound(right);
        auto s = mp.upper_bound(left - 1);
        if(s != mp.begin()) s--;
        while(s != e && s->second < left){s++;}
        if(s != e && s->second >= right && s->first <= left){
            return true;
        }
        return false;
    }
    
    void removeRange(int left, int right) {
        auto e = mp.upper_bound(right);
        auto s = mp.upper_bound(left - 1);
        if(s != mp.begin()) s--;
        vector<pair<int,int>> vec;
        while(s != e){
            auto temp = s;
            if(s->first < left){vec.push_back({s->first, min(left, s->second)});}
            if(s->second > right){vec.push_back({max(right, s->first),s->second});}
            s++;
            mp.erase(temp);
        }
        for(auto v : vec){
            mp.insert(e, v);
            e++;
        }
    }
    };
    

    /**

    • Your RangeModule object will be instantiated and called as such:
    • RangeModule obj = new RangeModule();
    • obj.addRange(left,right);
    • bool param_2 = obj.queryRange(left,right);
    • obj.removeRange(left,right);
      */

Log in to reply
 

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