C++ map 212ms


  • 0
    B

    I use a map to record the interval
    for add and remove range, I find all overlapped interval and erase them, then add one or two updated interval

    class RangeModule {
    public:
        map<int,int> _map;
        RangeModule() {
            
        }
        
        void addRange(int left, int right) {
            //cout << "add range " << left << " " << right << endl;
            unordered_set<int>to_del;
            auto it = _map.lower_bound(left);
            if(it != _map.begin()) it--;
            while(it != _map.end())
            {
                if(it -> second < left)
                {
                    it++;
                    continue;
                }
                if(it -> first > right) break;
                to_del.insert(it -> first);
                left = min(left, it -> first);
                right = max(right, it -> second);
                it++;
            }
            
            for(auto e : to_del) _map.erase(e);
            _map[left] = right;
        }
        
        bool queryRange(int left, int right) {
            //printMap();
            auto it = _map.lower_bound(left);
            if(it != _map.begin()) it--;
            while(it != _map.end())
            {
                if(it -> second < left)
                {
                    it++;
                    continue;
                }
                if(it -> first > right) return false;
                return it -> first <= left && it -> second >= right;
            }
            return false;
        }
        
        void removeRange(int left, int right) {
            //cout << "remove range " << left << " " << right << endl;
            unordered_set<int>to_del;
            auto it = _map.lower_bound(left);
            if(it != _map.begin()) it--;
            int v1 = -1, v2 = -1;
            while(it != _map.end())
            {
                if(it -> second <= left)
                {
                    it++;
                    continue;
                }
                if(it -> first >= right) break;
                if(it -> first < left)
                    v1 = it -> first;
                else
                    to_del.insert(it->first);
                if(it -> second > right) v2 = it -> second;
                it++;
            }
            for(auto e : to_del) _map.erase(e);
            if(v1 > 0) _map[v1] = left;
            if(v2 > 0) _map[right] = v2;
        }
        
        void printMap()
        {
            cout << "------ print map ------" << endl;
            for(auto e : _map) cout << e.first << " " << e.second << endl;
        }
    };
    
    /**
     * 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.