715. Range Module

Problem

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.

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

Implement the RangeModule class:

• RangeModule() Initializes the object of the data structure.

• void 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.

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

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

  Example 1:

Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

Explanation
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)

  Constraints:

• 1 <= left < right <= 10^9

• At most 10^4 calls will be made to addRange, queryRange, and removeRange.

Solution (Java)

class RangeModule {
    private final Interval head;

    public RangeModule() {
        head = new Interval(0, 0);
    }

    public void addRange(int left, int right) {
        Interval pos = head;
        while (pos.next != null && pos.next.end < left) {
            pos = pos.next;
        }
        while (pos.next != null && pos.next.start <= right) {
            left = Math.min(pos.next.start, left);
            right = Math.max(pos.next.end, right);
            removeNext(pos);
        }
        insert(pos, new Interval(left, right));
    }

    public boolean queryRange(int left, int right) {
        Interval pos = head;
        while (pos != null) {
            if (left >= pos.start && right <= pos.end) {
                return true;
            }
            pos = pos.next;
        }
        return false;
    }

    public void removeRange(int left, int right) {
        Interval pos = head;
        while (pos.next != null && pos.next.end <= left) {
            pos = pos.next;
        }
        Interval prev = pos;
        Interval curr = pos.next;
        while (curr != null && curr.start < right) {
            if (curr.start < left) {
                insert(prev, new Interval(curr.start, left));
                curr.start = left;
                prev = prev.next;
                curr = prev.next;
                continue;
            }
            if (right >= curr.end) {
                removeNext(prev);
                curr = prev.next;
            } else {
                curr.start = right;
                curr = curr.next;
            }
        }
    }

    private void insert(Interval curr, Interval next) {
        next.next = curr.next;
        curr.next = next;
    }

    private void removeNext(Interval curr) {
        Interval del = curr.next;
        if (del != null) {
            curr.next = del.next;
            del.next = null;
        }
    }

    static class Interval {
        int start;
        int end;
        Interval next;

        public Interval(int l, int r) {
            start = l;
            end = r;
        }
    }
}

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

Solution (C++)

class RangeModule {
public:
    RangeModule() {}

    void addRange(int left, int right) {
        IT l, r;
        getOverlapRanges(left, right, l, r);
        // At least one range overlapping with [left, right)
        if (l != r) {
            // Merge intervals into [left, right)
            auto last = r; --last;
            left = min(left, l->first);            
            right = max(right, last->second);
            // Remove all overlapped ranges
            ranges_.erase(l, r);
        }
        // Add a new/merged range
        ranges_[left] = right;
    }

    bool queryRange(int left, int right) {
        IT l, r;
        getOverlapRanges(left, right, l, r);
        // No overlapping range
        if (l == r) return false;
        return l->first <= left && l->second >= right;
    }

    void removeRange(int left, int right) {
        IT l, r;
        getOverlapRanges(left, right, l, r);
        // No overlapping range
        if (l == r) return;
        auto last = r; --last;
        int start = min(left, l->first);        
        int end = max(right, last->second);
        // Delete overlapping ranges        
        ranges_.erase(l, r);
        if (start < left) ranges_[start] = left;
        if (end > right) ranges_[right] = end;
    }
private:
    typedef map<int, int>::iterator IT;
    map<int, int> ranges_;
    void getOverlapRanges(int left, int right, IT& l, IT& r) {
        l = ranges_.upper_bound(left);
        r = ranges_.upper_bound(right);
        if (l != ranges_.begin())
            if ((--l)->second < left) l++;
    }
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).