You are planning a space route along a one-dimensional line (the x-axis).
You are given a list of planets. Each planet is represented by an integer pair (c,r):
-
c
is the coordinate of the planet's center on the x-axis.
-
r
is a non-negative integer radius of its gravitational influence.
A point x on the x-axis is unsafe for a space traveler if it lies within the gravitational influence of at least one planet:
∣x−ci∣≤rifor some planet i
Equivalently, each planet makes the interval [ci−ri,ci+ri] unsafe.
Task:
-
Consider the entire real line as the possible travel path.
-
Compute all
maximal continuous intervals
on this line where the traveler is
safe
, i.e., points not covered by any planet's unsafe interval.
-
Return these safe intervals as a sorted list of disjoint intervals.
Representation details:
-
Represent each safe interval as a pair
(start, end)
with
start < end
.
-
Intervals may be unbounded on the left or right:
-
Use
-∞
for an interval unbounded to the left (e.g.,
(-∞, a)
).
-
Use
+∞
for an interval unbounded to the right (e.g.,
(b, +∞)
).
You may assume the input list of planets can be in any order and may contain overlapping or nested gravitational ranges. Return the safe intervals in increasing order of start.