Problem Explanation

The problem involves creating a range tracker that keeps track of ranges of real numbers. We are required to create three methods:

• addRange(left, right) : This method adds the half-open range [left, right), including every real number within this range. If a range partially overlaps with the current range, only the numbers not already tracked are added.

• queryRange(left, right) : This method checks if every real number within the interval [left, right) is being tracked. It returns true if all the numbers are being tracked, otherwise returns false.

• removeRange(left, right) : This method stops tracking every real number currently being tracked in the interval [left, right).

It is important to note that 0 < left < right < 10^9 in all calls to these methods.

Solution Approach

The problem could be solved by using a data structure called Segment Tree with lazy propagation. The root of the Segment Tree represents the entire range of numbers, and each node represents an interval of this range. A leaf node represents a smallest possible interval (single element in this case).

In this solution, we use Segment Tree to divide an interval into two halves until we reach the target interval [left, right).

• In addRange(left, right), we update the Segment Tree nodes that fall into the interval [left, right), and mark them as "tracked". If a node's interval is completely included in [left, right), we mark this node as "tracked" and delete its children to save space.

• In queryRange(left, right), we check if all nodes in the interval are marked as "tracked". If we encounter a "not tracked" node or the node's interval is not completely included in [left, right), we continue our search on its children.

• In removeRange(left, right), we follow the same process as addRange(left, right), with the difference that we mark the nodes as "not tracked".

Example

Let's take an example to illustrate this:

Example:

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

In this example, the first operation addRange(10, 20) adds the numbers from 10 to 19 into the range. The tracking status for these numbers is updated in the Segment Tree.

Then, removeRange(14, 16) stops tracking the numbers from 14 to 15.

When performing the query queryRange(10, 14), all numbers from 10 to 13 are found to be tracked, so the result is true.

When performing the query queryRange(13, 15), the number 14 is found to be not tracked, so the result is false.When performing the query queryRange(16, 17), although the removeRange(14, 16) operation was performed previously, the number 16 is found to be tracked (since 16 is not included in the remove range), so the result is true.

Solutions with Python, Java and JS

Python Solution

1
2python
3from sortedcontainers import SortedList
4class RangeModule:
5    def __init__(self):
6        self.ranges = SortedList()
7
8    def _bounds(self, left, right):
9        i = self.ranges.bisect_left((left))
10        j = self.ranges.bisect_right((right))
11        return i, j, i < j and self.ranges[i][0] < right and left < self.ranges[j - 1][1]
12
13    def addRange(self, left: int, right: int) -> None:
14        i, j, overlap = self._bounds(left, right)
15        if not overlap:
16            left = min(left, self.ranges[i - 1][1] if i - 1 >= 0 else left)
17            right = max(right, self.ranges[j][0] if j < len(self.ranges) else right)
18            self.ranges[i:j] = [(left, right)]
19
20    def queryRange(self, left: int, right: int) -> bool:
21        i, j, overlap = self._bounds(left, right)
22        return overlap
23
24    def removeRange(self, left: int, right: int) -> None:
25        i, j, overlap = self._bounds(left, right)
26        if overlap:
27            if self.ranges[i][0] < left:
28                self.ranges.insert(i, (self.ranges[i][0], left))
29                i += 1
30            if right < self.ranges[j - 1][1]:
31                self.ranges.insert(j, (right, self.ranges[j - 1][1]))
32            self.ranges[i:j] = []

Java Solution

1
2java
3import java.util.Map;
4import java.util.TreeMap;
5
6public class RangeModule {
7    private TreeMap<Integer, Integer> map;
8    
9    public RangeModule() {
10        map = new TreeMap<>();
11    }
12    
13    public void addRange(int left, int right) {
14        if (right <= left) return;
15        Integer start = map.floorKey(left);
16        Integer end = map.floorKey(right);
17        if (start == null && end == null) {
18            map.put(left, right);
19        } else if (start != null && map.get(start) >= left) {
20            map.put(start, Math.max(map.get(end), Math.max(map.get(start), right)));
21        } else {
22            map.put(left, Math.max(map.get(end), right));
23        }
24        // clean up intermediate intervals
25        Map<Integer, Integer> subMap = map.subMap(left, false, right, true);
26        while (!subMap.isEmpty()) {
27            map.remove(subMap.entrySet().iterator().next().getKey());
28        }
29    }
30    
31    public boolean queryRange(int left, int right) {
32        Integer start = map.floorKey(left);
33        if (start == null) return false;
34        return map.get(start) >= right;
35    }
36    
37    public void removeRange(int left, int right) {
38        if (right <= left) return;
39        Integer start = map.floorKey(left);
40        Integer end = map.floorKey(right);
41        if (end != null && map.get(end) > right) {
42            map.put(right, map.get(end));
43        }
44        if (start != null && map.get(start) > left) {
45            map.put(start, left);
46        }
47        // clean up intermediate intervals
48        Map<Integer, Integer> subMap = map.subMap(left, true, right, false);
49        while (!subMap.isEmpty()) {
50            map.remove(subMap.entrySet().iterator().next().getKey());
51        }
52    }
53}

JavaScript Solution

1
2javascript
3class RangeModule {
4    constructor() {
5        this.range = [];
6    }
7    _find(i) {
8		let l = 0, r = this.range.length - 1;
9		while(l <= r) {
10			let mid = Math.floor((r + l) / 2);
11			if(this.range[mid][1] < i) l = mid + 1;
12			else r = mid - 1;
13		}
14		return l;
15	}
16	addRange(left, right) {
17		let start = this._find(left), end = this._find(right);
18		if(start > end && this.range[start - 1][1] >= left) start--;
19		let merged = [left, right];
20		if(start > 0 && this.range[start - 1][1] >= left) merged[0] = this.range[start - 1][0];
21		if(end < this.range.length && this.range[end][0] <= right) merged[1] = this.range[end--][1]
22		this.range.splice(start, end - start + 1, merged);
23	}
24	queryRange(left, right) {
25		let index = this._find(left);
26		return (index < this.range.length && right <= this.range[index][1]);
27	}
28	removeRange(left, right) {
29		let start = this._find(left), end = this._find(right);
30		if(start > end && this.range[start - 1][1] >= left) start--;
31		let range = [];
32		if(start < this.range.length && this.range[start][0] < left) range.push([this.range[start][0], left]);
33		if(end < this.range.length && this.range[end][1] > right) range.push([right, this.range[end][1]])
34		this.range.splice(start, end - start + 1, ...range);
35	}
36}

These solutions use the approach of maintaining a list of sorted intervals and finding the correct place to insert, remove or update an interval. It provides O(log n) time complexity for each operation.