Range Module Problem


Description

LeetCode Problem 715.

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:

1
2
3
4
5
6
7
8
9
10
11
12
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.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class RangeModule {
public:
    map<int, int> m;
    
    void addRange(int left, int right) {
        auto it = m.upper_bound(left);
        if (it != begin(m) && prev(it)->second >= left)
            left = prev(it)->first;
        m.insert({left, removeIntervals(left, right)});
    }
    
    bool queryRange(int left, int right) {
        auto it = m.upper_bound(left);
        if (it != begin(m))
            it = prev(it);
        return left >= it->first && right <= it->second;
    }
    
    void removeRange(int left, int right) {
        int right1 = removeIntervals(left, right);
        auto it = m.lower_bound(left);
        if (it != begin(m)) {
            right1 = max(right1, prev(it)->second);
            prev(it)->second = min(prev(it)->second, left);
        }
        if (right1 > right)
            m.insert({right, right1});
    }
    
    int removeIntervals(int l, int r) {
        for (auto it = m.lower_bound(l); it != end(m) && it->first <= r; ) {
            r = max(r, it->second);
            m.erase(it++);
        }
        return r;
    }
};
/**
 * 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);
 */




Related Posts

Time Based Key-Value Store Problem

LeetCode 981. Design a time-based key-value data structure that can...

Rle Iterator Problem

LeetCode 900. We can use run-length encoding (i.e., RLE) to...

Online Stock Span Problem

LeetCode 901. Design an algorithm that collects daily price quotes...

Online Election Problem

LeetCode 911. You are given two integer arrays persons and...

Number Of Recent Calls Problem

LeetCode 933. You have a RecentCounter class which counts the...

Maximum Frequency Stack Problem

LeetCode 895. Design a stack-like data structure to push elements...