区间问题
本文最后更新于:2024年2月12日 晚上
动态增添区间和删除区间
class RangeModule {
// 保存区间的左右端点
TreeMap<Integer, Integer> map = new TreeMap<>();
public RangeModule() {
}
public void addRange(int left, int right) {
Integer L = map.floorKey(right);
int l = left, r = right;
// 合并区间
while (L != null && map.get(L) >= l) {
l = Math.min(l, L);
r = Math.max(r, map.get(L));
map.remove(L);
L = map.floorKey(right);
}
map.put(l, r);
}
public boolean queryRange(int left, int right) {
Integer L = map.floorKey(left);
return L != null && map.get(L) >= right;
}
public void removeRange(int left, int right) {
Map.Entry<Integer, Integer> en = map.lowerEntry(left);
// 与左边区间有交集
if (en != null && en.getValue() > left) {
map.put(en.getKey(), left);
if (en.getValue() > right) {
map.put(right, en.getValue());
return;
}
}
while (true) {
en = map.ceilingEntry(left);
// 与右边区间有交集
if (en != null && en.getKey() < right) {
// 该区间被完全包含,直接移除该区间
map.remove(en.getKey());
// 该区间右端点超过right,保留right~右端点这段区间
if (en.getValue() > right) {
map.put(right, en.getValue());
return;
}
} else {
break;
}
}
}
}
本文作者: MerickBao
本文链接: https://merickbao.top/post/%E7%AE%97%E6%B3%95/%E5%9F%BA%E7%A1%80%E7%9F%A5%E8%AF%86/%E5%8C%BA%E9%97%B4%E9%97%AE%E9%A2%98.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!