用有序集合插入、删除、合并、查询区间，求解《715. Range 模块》
例题
715. Range 模块
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
实现 RangeModule 类:
RangeModule() 初始化数据结构的对象。
void addRange(int left, int right) 添加 半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true ，否则返回 false 。
void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
答案
有序集合
class RangeModule {
TreeMap<Integer, Integer> map = new TreeMap<>();
public void addRange(int left, int right) {
int start = left, end = right;
Map.Entry<Integer,Integer> cur = map.floorEntry(right);
while (cur != null && cur.getValue() >= left){ // 相交，取并集
map.remove(cur.getKey());
if (cur.getValue() > right) end = cur.getValue();
if (cur.getKey() < left) start = cur.getKey();
cur = map.floorEntry(right);
}
map.put(start, end);
}
public boolean queryRange(int left, int right) {
Integer key = map.floorKey(left);
if (key == null) return false;
return map.get(key) >= right;
}
public void removeRange(int left, int right) {
Map.Entry<Integer, Integer> cur = map.lowerEntry(right);
while (cur != null && cur.getValue() > left){
map.remove(cur.getKey());
if (cur.getValue() > right) map.put(right, cur.getValue());
if (cur.getKey() < left) map.put(cur.getKey(), left);
cur = map.lowerEntry(right);
}
}
}class RangeModule {
private TreeMap<Integer, Integer> m = new TreeMap<Integer, Integer>();
public RangeModule() {}
private Integer getL(int left) {
Integer l = m.floorKey(left);
if (l == null && m.isEmpty() == false) l = m.firstKey();
return l;
}
public void addRange(int left, int right) {
Integer l = getL(left);
if (l != null) {
Integer r = m.get(l);
if (left >= l) {
if (right <= r) return;
if (left <= r) {
m.remove(l);
left = l;
}
}
}
while (l != null && l <= right) {
Integer r = m.get(l);
if (r != null && r > left) {
right = Math.max(right, r);
m.remove(l);
}
l = m.higherKey(l);
}
m.put(left, right);
}
public boolean queryRange(int left, int right) {
Integer l = getL(left);
while (l != null && l <= left) {
Integer r = m.get(l);
if (left >= l && right <= r) return true;
l = m.higherKey(l);
}
return false;
}
public void removeRange(int left, int right) {
Integer l = getL(left);
if (l != null) {
Integer r = m.get(l);
if (left >= l) {
if (right <= r) {
m.remove(l);
if (left > l) m.put(l, left);
if (right < r) m.put(right, r);
return;
}
if (left < r) {
if (left > l) m.put(l, left);
}
}
}
while (l != null && l < right) {
Integer r = m.get(l);
if (r > left) {
m.remove(l);
if (r > right) m.put(right, r);
}
l = m.higherKey(l);
}
}
}