Problem description:

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
13
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 <= 109
  • At most 104 calls will be made to addRange, queryRange, and removeRange.

Solution:

原本紀錄區間是[(1,2),(3,5),(8,12)]

但可改為紀錄是：[1,2,3,5,8,12]

经过这样的处理， 数组的奇数坐标就是区间的结束点，偶数坐标就是开始点

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
addRange(10, 20) -> [10, 20]
removeRange(14,16) -> [10,14,16,20]
queryRange(10,14) True
queryRange(13,15) False
queryRange(16,17) True
removeRange(13,15) [10,13,16,20]

--add(10,20)--
[] 0 0
[10, 20]
--remove(14,16)--
[10, 20] 1 1
[10, 14, 16, 20]
--query(10,14)--
[10, 14, 16, 20] 1 1
--query(13,15)--
[10, 14, 16, 20] 1 2
--query(16,17)--
[10, 14, 16, 20] 3 3
--remove(13,15)--
[10, 14, 16, 20] 1 2
[10, 13, 16, 20]
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
class RangeModule:
    def __init__(self):
        self._X = []
    def addRange(self, left, right):
        i, j = bisect_left(self._X, left), bisect_right(self._X, right)
        print("--add--")
        print(self._X, i, j)
        self._X[i:j] = [left] * (i%2 == 0) + [right] * (j%2 == 0)
        print(self._X)
    def queryRange(self, left, right):
        
        i, j = bisect_right(self._X, left), bisect_left(self._X, right)
        print("--query--")
        print(self._X, i, j)
        return i == j and i%2 == 1
    def removeRange(self, left, right):
        
        i, j = bisect_left(self._X, left), bisect_right(self._X, right)
        print("--remove--")
        print(self._X, i, j)
        self._X[i:j] = [left]*(i%2 == 1) + [right]*(j%2 == 1)
        print(self._X)
        
        """
                           bisect
        idx          0   1   2   3   4         
        arr        [   1---4   7---9   ]
        """

time complexity:
addRange: $O(n)$
removeRange: $O(n)$
queryRange: $O(logn)$
space complexity: $O()$
reference:
related problem: