区间问题

本文最后更新于:2024年2月12日 晚上

56. 合并区间

57. 插入区间

2276. 统计区间中的整数数目

715. Range 模块

动态增添区间和删除区间

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;
            }
        }
    }
}