C++ O(nlogn) based on disjoint intervals data structure


  • 5
    E
    class RangeModule {
    public:
        set<pair<int,int>> s;
        RangeModule() {}
        
        void addRange(int x, int y) {
            auto it = s.upper_bound({x,INT_MAX});
            if (it != s.begin()){
                // if previous interval overlap merge and delete
                if ((--it)->second < x) ++it;
                else {
                    x = it->first;
                    y = max(it->second,y);
                    it = s.erase(it);
                }
            }
            // while overlapping merge and delete
            while (it != s.end() && it->first <= y) {
                y = max(y,it->second);
                it = s.erase(it);
            }
            s.insert({x,y});
        }
        
        bool queryRange(int x, int y) {
            auto it = s.upper_bound({x,INT_MAX});
            return (it != s.begin() && (--it)->second >=y);
        }
        
        void removeRange(int x, int y) {
            auto it = s.upper_bound({x,INT_MAX});
            vector<pair<int,int>> to;
            if (it != s.begin()){
                if ((--it)->second <= x) ++it;
                else {
                    // if previous interval overlap remove but add back the portion still covered
                    to.push_back({it->first, x});
                    if (it->second > y) to.push_back({y, it->second});
                    it = s.erase(it);
                }
            }
            // while overlapping remove
            // if one of the removed intervals is partially covered by the remove range, add back the uncovered portion
            while (it != s.end() && it->first < y) {
                if (it->second > y) to.push_back({y, it->second});
                it = s.erase(it);
            }
            for (auto p : to) s.insert(p);
        }
    };
    

Log in to reply
 

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