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

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

这道题要求你设计一个区间集合（IntervalSet），本质上是维护一组不断合并的区间，并支持插入新区间以及判断某个值是否落在任一区间内。常见做法是用有序结构保存不相交区间，在插入时找到与新区间重叠或相邻的片段并合并；查询时则利用二分或平衡树快速定位目标值所在的区间。重点在于如何高效维护“区间并集”的不重叠表示，从而让插入和查询都保持较好的时间复杂度。