公司宣布降薪20%，同事因房贷压力拒绝接受，结果领导却说:不是非要大家接受，不接受可以选择走人

面试题：Range 模块

Range 模块最容易出 bug 的地方，不是 TreeMap 用不会，是边界没想清楚。

线上真要遇到这种东西，一般不是叫 Range Module，名字会包装得很好听：权益覆盖范围、时间段占用、IP 白名单段、优惠券可用区间、库存锁定区间。日志里看起来就一行：

range_check miss, userId=38127, ask=[1200,1500), current=[[800,1200),[1500,2000)]

这行我第一眼就不会去翻业务流程。

我会先问一句：你们这个区间到底包不包右边界？

很多代码坏就坏在这里。需求嘴上说“1200 到 1500”，开发脑子里是 [1200,1500]，存储时又写成 [1200,1500)，最后查的时候 > 和 >= 混着来。

我一般直接把规则定死：左闭右开。

也就是 [left, right)。

这样有个好处，两个连续区间 [10,20) 和 [20,30) 可以无缝拼起来，不会纠结 20 到底算谁的。

Range 模块一般就三个动作：

addRange(left, right)
queryRange(left, right)
removeRange(left, right)

别急着写代码，先看一组现场数据。

add [10, 20)
add [30, 40)
add [18, 32)

最后应该变成：
[10, 40)

这不是新增，这是合并。

再看删除：

current: [10, 40)
remove : [18, 32)

最后应该变成：
[10, 18), [32, 40)

这不是删除，这是切割。

我见过不少代码，新增能合并，删除一切割就乱了。尤其是删中间一段，原来的一个区间要拆成两个，这地方最容易漏。

下面这个实现我会用 TreeMap，key 放区间左端点，value 放右端点。

import java.util.Map;
import java.util.TreeMap;

publicclassRangeBox{

// key: left, value: right，统一按 [left, right) 存
privatefinal TreeMap<Integer, Integer> ranges = new TreeMap<>();

publicvoidaddRange(int left, int right){
if (left >= right) {
return;
        }

        Map.Entry<Integer, Integer> hit = ranges.floorEntry(left);
if (hit != null && hit.getValue() >= left) {
            left = Math.min(left, hit.getKey());
            right = Math.max(right, hit.getValue());
            ranges.remove(hit.getKey());
        }

        Map.Entry<Integer, Integer> next = ranges.ceilingEntry(left);
while (next != null && next.getKey() <= right) {
            right = Math.max(right, next.getValue());
            ranges.remove(next.getKey());
            next = ranges.ceilingEntry(left);
        }

        ranges.put(left, right);
    }

publicbooleanqueryRange(int left, int right){
if (left >= right) {
returntrue;
        }

        Map.Entry<Integer, Integer> hit = ranges.floorEntry(left);
return hit != null && hit.getValue() >= right;
    }

publicvoidremoveRange(int left, int right){
if (left >= right) {
return;
        }

        Map.Entry<Integer, Integer> hit = ranges.floorEntry(left);
if (hit != null && hit.getValue() > left) {
int oldLeft = hit.getKey();
int oldRight = hit.getValue();
            ranges.remove(oldLeft);

if (oldLeft < left) {
                ranges.put(oldLeft, left);
            }
if (oldRight > right) {
                ranges.put(right, oldRight);
            }
        }

        Map.Entry<Integer, Integer> next = ranges.ceilingEntry(left);
while (next != null && next.getKey() < right) {
int oldLeft = next.getKey();
int oldRight = next.getValue();
            ranges.remove(oldLeft);

if (oldRight > right) {
                ranges.put(right, oldRight);
break;
            }

            next = ranges.ceilingEntry(left);
        }
    }

public String dump(){
return ranges.toString();
    }
}

这段代码里有几个判断，别随手改。

addRange 里面：

hit.getValue() >= left

这里用的是 >=，因为 [10,20) 和 [20,30) 在业务上可以合并成 [10,30)。如果你的业务认为两个区间必须隔开，那这里就要改成 >。

但大部分 Range 模块，连续区间合并更省事。

removeRange 里面第一段处理的是“左边盖住了删除起点”的区间。

比如：

current: [10, 40)
remove : [18, 32)

floorEntry(18) 能找到 [10,40)。这时候不能简单删掉 [10,40)，要拆：

[10,18)
[32,40)

所以代码里才有这两句：

if (oldLeft < left) {
    ranges.put(oldLeft, left);
}
if (oldRight > right) {
    ranges.put(right, oldRight);
}

这两句少任何一句，数据都会丢一截。

我一般会补一个很土的测试，不靠脑补。

publicclassRangeBoxCheck{

publicstaticvoidmain(String[] args){
        RangeBox box = new RangeBox();

        box.addRange(10, 20);
        box.addRange(30, 40);
        box.addRange(18, 32);

        System.out.println(box.dump()); 
// {10=40}

        System.out.println(box.queryRange(10, 40)); 
// true

        box.removeRange(18, 32);

        System.out.println(box.dump()); 
// {10=18, 32=40}

        System.out.println(box.queryRange(10, 18)); 
// true

        System.out.println(box.queryRange(18, 32)); 
// false
    }
}

Range 模块还有个坑，出在“查询”。

有人会这么写：

return ranges.containsKey(left) && ranges.get(left) >= right;

这个写法看着挺直，其实不行。

因为你查 [15,18)，当前只有 [10,20)，它明明被覆盖了，但 containsKey(15) 是 false。

所以查询必须用：

ranges.floorEntry(left)

找左端点小于等于 left 的那个区间，再看它的右端点能不能盖住 right。

这就是 Range 模块的关键动作：往左找一个，再往右吞一串。

新增是这样。

删除也是这样。

查询还是这样。

复杂度也还可以。TreeMap 底层是红黑树，查一次是 O(log n)，合并和删除时会额外扫掉被影响的区间。正常业务里区间数量不会无限大，比拿数组一格一格扫靠谱得多。

不过这玩意别随便套到所有场景。

如果你的区间范围特别小，比如只管一天 24 小时、分钟级标记，总共也就 1440 个点，用 boolean 数组反而简单。

如果区间范围特别大，更新又特别频繁，还要持久化，那就别只盯着内存结构了。得考虑数据库怎么存，怎么加索引，多个实例同时更新时怎么加锁。Range 逻辑本身不难，难的是别让两个请求同时把区间切坏。

我一般会在更新前后打一条很克制的日志：

log.info("range_change bizId={}, op={}, ask=[{},{}), before={}, after={}",
        bizId, op, left, right, before, rangeBox.dump());

不要每次查询都打，量一上来日志能把磁盘打满。只打变更，排问题够用了。

Range 模块写到最后，其实就记住一个规矩：边界统一，别混用；新增要合并，删除要切割；查询别只盯着当前 left，往左找一下。

很多 bug 不是算法不会，是一开始就没把 [left,right) 这件事钉死。