leetcode-go/leetcode/hard/715.cc

#include <algorithm>
#include <vector>

#include <iostream>

using std::make_pair;
using std::pair;
using std::vector;

using std::cout; using std::endl;

class RangeModule {
public:
    RangeModule() {
    }

    void addRange(int left, int right) {
        vector<pair<int, int> > result;
        auto it = segments.begin();
        for (; it != segments.end() && it->first < left; ++it);
        segments.insert(it, make_pair(left, right));
        for (it = segments.begin(); it != segments.end(); ++it) {
            if (result.size() == 0 || result.back().second < it->first)
                result.push_back(*it);
            else
                result.back().second = std::max(result.back().second, it->second);
        }
        segments = result;
    }

    bool queryRange(int left, int right) {
        for (auto it = segments.begin(); it != segments.end() && left != right; ++it) {
            if (it->second <= left || right <= it->first)
                continue;
            if (it->first <= left && right <= it->second)
                return true;
            if (left < it->first)
                return false;
            left = std::min(it->second, right);
        }
        return left == right;
    }

    void removeRange(int left, int right) {
        vector<pair<int, int> > result;
        for (auto it = segments.begin(); it != segments.end(); ++it) {
            if (right <= it->first || it->second <= left) {
                result.push_back(*it);
                continue;
            }
            if (left <= it->first && it->second <= right)
                continue;
            if (it->first < left)
                result.push_back(make_pair(it->first, left));
            if (right < it->second)
                result.push_back(make_pair(right, it->second));
        }
        segments = result;
    }

    void printRange() {
        for (auto it = segments.begin(); it != segments.end(); ++it)
            cout << it->first << ":" << it->second << "; ";
        cout << endl;
    }

private:
    vector<pair<int, int> > segments;
};

/**
 * 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);
 */

// 0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange
// 1000000000

int main() {
    RangeModule *obj = new RangeModule();

    obj->addRange(6, 8);
    obj->removeRange(7, 8);
    obj->removeRange(8, 9);
    obj->addRange(8, 9);
    obj->removeRange(1, 3);
    obj->printRange();
    obj->addRange(1, 8);

    obj->printRange();
    bool param_1 = obj->queryRange(2, 4) == true;
    bool param_2 = obj->queryRange(2, 9) == true;
    bool param_3 = obj->queryRange(4, 6) == true;

    cout << param_1 << " " << param_2 << " " << param_3 << endl;

    return 0;
}