Google VO 面试真题解析：Design and Implement an IntervalSet（Union of Ranges）

Google 的 VO 里，IntervalSet（区间并集）这类题通常不会只停在「能不能写出插入和查询」，而是顺着追问把复杂度、合并时机和数据结构选择一路聊下去。本文把它拆成题目、思路、两种实现和边界讨论，方便在有限时间里讲清楚。

题目描述

Design and implement an IntervalSet, also known as a union of ranges. The IntervalSet should support:

Inserting intervals
Querying whether a particular value is contained

本质是维护一组「不断合并的区间」，支持插入新区间、判断某个值是否落在任一区间内。区间可以重叠或相邻，重叠/相邻的区间要合并成一个更大的区间，最终集合里任意两个区间都不相交、也不接触。

解题思路

核心是维护「区间并集」的不重叠表示。用一个有序结构保存当前所有不相交区间（按起点升序），插入时定位到与新区间重叠或相邻的片段，把它们合并成一个再放回集合；查询时用二分定位目标值可能落入的区间，检查终点即可。

两条不变量要守住：

集合内任意两个区间不重叠、不相邻，否则就应该合并。
区间始终按起点升序排列，查询才能二分。

数据结构选择

1. 有序数组 + 二分（Python list + bisect）：contains 是 O(log n)，insert 需要移动数组元素、最坏 O(n)，但实现最简单，适合先写正确版本。 2. 平衡树（C++ std::map / TreeMap / 跳表）：insert 与 contains 都是 O(log n)，合并 k 个区间时为 O(log n + k)；用「起点到终点」的映射，插入时用 lower_bound 找重叠邻居。

代码实现

Python 标准库版（有序数组 + 二分）：

import bisect

class IntervalSet:
    def __init__(self):
        self.starts = []   # 有序、互不相交区间的起点
        self.ends = []     # 对应终点

    def insert(self, start, end):
        if start > end:
            return
        # 与 [start, end] 重叠或相邻的区间：ends[i] >= start - 1 且 starts[j] <= end + 1
        i = bisect.bisect_left(self.ends, start - 1)
        j = bisect.bisect_right(self.starts, end + 1)
        if i < j:
            start = min(start, self.starts[i])
            end = max(end, self.ends[j - 1])
            del self.starts[i:j]
            del self.ends[i:j]
        self.starts.insert(i, start)
        self.ends.insert(i, end)

    def contains(self, value):
        idx = bisect.bisect_right(self.starts, value) - 1
        return idx >= 0 and self.ends[idx] >= value

说明一下相邻合并：整数区间 [1,2] 和 [3,4] 之间没有空隙，union of ranges 通常会把它们合成 [1,4]。代码里用 start - 1 和 end + 1 作为比较边界，就是为了把「相邻」也算进合并范围；如果题目规定相邻不合并，把这两个边界改回 start 和 end 即可。

复杂度分析

contains 两次 bisect 都是 O(log n)，判定 O(1)，总计 O(log n)。insert 的定位是 O(log n)，但 del 和 insert 在数组中间需要搬动元素，最坏 O(n)。空间为 O(n)，n 是当前不相交区间的数量。这个版本胜在简单可靠，适合先交出正确结果。

进阶：平衡树 O(log n) 版本

如果面试追问「插入能不能更快」，说明数组版的瓶颈在中间搬移，换成按 key 排序的平衡树就能把 insert 压到 O(log n + k)（k 为本次合并掉的区间数）。以 C++ std::map（key=起点，value=终点）为例：

class IntervalSet {
    std::map<long long, long long> mp; // start -> end
public:
    void insert(long long s, long long e) {
        if (s > e) return;
        auto it = mp.lower_bound(s - 1);
        while (it != mp.end() && it->first <= e + 1) {
            s = std::min(s, it->first);
            e = std::max(e, it->second);
            it = mp.erase(it);
        }
        mp[s] = e;
    }
    bool contains(long long v) {
        auto it = mp.upper_bound(v);
        if (it == mp.begin()) return false;
        --it;
        return it->second >= v;
    }
};

lower_bound(s-1) 找到第一个「终点可能触及新区间」的区间，向右循环合并所有起点不超过 e+1 的区间，删除后插入合并结果。contains 用 upper_bound 找到第一个起点大于 v 的区间，回退一位检查其终点。

易错点与边界

相邻是否合并要提前问清。整数区间通常「相邻即合并」，闭区间 [1,2] 与 [3,4] 合成 [1,4]；若规定不合并，比较边界改用 start 和 end。
空插入：start 大于 end 时直接返回，别让非法区间污染集合。
单点区间：start 等于 end 是合法区间，查询边界要用 bisect_right 或 upper_bound，避免漏判「value 恰好等于某个起点」的情况。
查询落在缝隙：value 在两个区间之间时，idx 定位到左区间，必须再检查 ends[idx] >= value，否则会误判为包含。

追问方向

1. 区间端点是浮点数时「相邻」怎么定义？通常改为仅重叠合并，相邻用 epsilon 判断或直接不合并。 2. 要支持删除区间或查询区间总长度？需要在集合上额外维护长度总和，删除时做差集拆分。 3. 查询要返回覆盖该点的区间本身而不是布尔值？contains 改为返回定位到的 [start, end] 或 None。

备考建议

先写数组版保证正确，再解释瓶颈并切换到平衡树版。手推一组包含「重叠、相邻、缝隙、单点」四类输入的样例，确认合并边界和二分回退逻辑都正确。

FAQ

为什么相邻区间也要合并？

union of ranges 关心的是「值是否落在并集里」，[1,2] 与 [3,4] 之间没有空隙，合并成 [1,4] 后并集不变、区间更少，查询更省。

contains 为什么要用 upper_bound 回退一位？

先找到第一个起点大于 value 的区间，它的前一个区间才可能覆盖 value；再检查前一个区间的终点是否不小于 value，避免漏掉 value 恰好等于某区间起点的情况。

insert 用数组实现一定是 O(n) 吗？

定位是 O(log n)，但合并要在数组中间删除若干区间并插入一个，list 的搬移成本是 O(n)。用平衡树才能把整体降到 O(log n + k)。

参考来源

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

微信：Coding0201
邮箱：[email protected]
Telegram：@OAVOProxy
WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。