行星引力区间：合并危险范围后取补集

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 可辨题给每颗行星(center,radius)，危险是[c−r,c+r]；未给有限查询域。
• 代码采用整数坐标、整数非负半径、闭域[low,high]，返回闭合安全整数段。实数版不可使用±1，需表达开闭端点和无穷。

解题路线

1. 先裁剪危险区间到查询域，按左端点排序；cursor代表尚未决定的最小整数。
2. 当a>cursor时输出[cursor,a−1]；把cursor推进到max(cursor,b+1)。重叠、包含、相接区间由cursor自然合并。扫完输出剩余尾段。
3. 实数全轴补集要给(−∞,firstLeft)、相邻危险并集之间的开区间及(lastRight,+∞)，危险端点不属于安全域。不能把整数训练输出误用到连续航线。

手动走一遍

危险[2,4]和[4,6]，查询整数[0,8]，安全[0,1]与[7,8]。零半径危险[3,3]仍排除3；实数域会切出两个开端点区间，整数域才用2/4。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def safe_ranges(planets,low,high):
    # Integer coordinates, closed query domain and closed hazard intervals.
    if low>high:raise ValueError("invalid query domain")
    intervals=[]
    for center,radius in planets:
        if radius<0:raise ValueError("negative radius")
        a,b=max(low,center-radius),min(high,center+radius)
        if a<=b:intervals.append((a,b))
    cursor=low;answer=[]
    for a,b in sorted(intervals):
        if a>cursor:answer.append((cursor,a-1))
        cursor=max(cursor,b+1)
    if cursor<=high:answer.append((cursor,high))
    return answer

复杂度

n行星O(nlogn)时间/O(n)区间与结果空间。输入已按危险左端排序则O(n)。

易错点与追问

容易失分的边界

• center排序不保证center−radius排序。
• 没有有限域时只返回首尾有限段会丢两侧无限安全区域。

继续深挖

• 持续新增行星时怎样维护有序区间并集？
• 若危险条件是距离严格小于r，安全端点标志怎样变化？