0715. Range Module
https://leetcode.com/problems/range-module
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)
Returnstrue
if every real number in the interval[left, right)
is currently being tracked, andfalse
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 <= 109
At most
104
calls will be made toaddRange
,queryRange
, andremoveRange
.
ac
class RangeModule {
TreeMap<Integer, Integer> tmap;
public RangeModule() {
tmap = new TreeMap<>();
}
public void addRange(int left, int right) {
// clean
clean(left, right);
Integer floor = tmap.floorKey(left);
Integer ceil = tmap.ceilingKey(right);
if (floor == null || tmap.get(floor) == 1) {
tmap.put(left, 0); // add start point
}
if (ceil == null || tmap.get(ceil) == 0) {
tmap.put(right, 1);
}
}
public boolean queryRange(int left, int right) {
Integer floor = tmap.floorKey(left);
if (floor == null || tmap.get(floor) != 0) return false;
Map<Integer, Integer> sub = tmap.subMap(left, false, right, false);
return sub.size() == 0;
}
public void removeRange(int left, int right) {
clean(left, right);
Integer floor = tmap.floorKey(left);
Integer ceil = tmap.ceilingKey(right);
if (floor != null && tmap.get(floor) == 0) {
tmap.put(left, 1);
}
if (ceil != null && tmap.get(ceil) == 1) {
tmap.put(right, 0);
}
}
public void clean(int left, int right) {
Map<Integer, Integer> sub = tmap.subMap(left, true, right, true);
Set<Integer> set = new HashSet<>(sub.keySet());
tmap.keySet().removeAll(set);
}
}
/**
* 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);
*/
/*
1) treemap record start/end point; 2) add/remove, clean first, then add start/end point;
*/
Last updated
Was this helpful?