715

715. Range Module (Hard)

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.

queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.

removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Example 1:

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Note:

A half open interval [left, right) denotes all real numbers left <= x < right.

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

The total number of calls to addRange in a single test case is at most 1000.

The total number of calls to queryRange in a single test case is at most 5000.

The total number of calls to removeRange in a single test case is at most 1000.

Companies:
Google, Amazon, Facebook

Related Topics:
Segment Tree, Ordered Map

Similar Questions:

• Merge Intervals (Medium)
• Insert Interval (Medium)
• Data Stream as Disjoint Intervals (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/range-module/
// Author: github.com/lzl124631x
// Time: 
//      RangeModule: O(1)
//      addRange: O(N)
//      queryRange: O(logN)
//      removeRange: O(N)
// Space: O(N)
class RangeModule {
    map<int, int> m;
public:
    RangeModule() {}
    void addRange(int left, int right) {
        auto it = m.lower_bound(left);
        if (it != begin(m) && prev(it)->second >= left) --it;
        if (it != end(m)) left = min(left, it->first);
        while (it != end(m) && it->first <= right) {
            if (it->second <= right) it = m.erase(it);
            else {
                right = it->second;
                it = m.erase(it);
                right = it->second;
                break;
            }
        }
        m[left] = right;
    }
    bool queryRange(int left, int right) {
        auto it = m.lower_bound(left);
        if (it != begin(m) && prev(it)->second > left) --it;
        if (it == end(m)) return false;
        return it->first <= left && it->second >= right;
    }
    void removeRange(int left, int right) {
        auto it = m.lower_bound(left);
        if (it != begin(m) && prev(it)->second > left) {
            --it;
            int r = it->second;
            it->second = left;
            if (right < r) {
                m[right] = r;
                return;
            }
            ++it;
        }
        while (it != end(m) && it->first < right) {
            if (it->second <= right) it = m.erase(it);
            else {
                int r = it->second;
                m.erase(it);
                m[right] = r;
                break;
            }
        }
    }
};

TODO

Hard to get it right. Learn https://leetcode.com/problems/range-module/discuss/108912/C%2B%2B-vector-O(n)-and-map-O(logn)-compare-two-solutions