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 - c_i| \le r_i \quad \text{for some planet } i ]
Equivalently, each planet makes the interval ([c_i - r_i,; c_i + r_i]) unsafe.
Task:
Representation details:
(start, end)
with
start < end
.
-∞
for an interval unbounded to the left (e.g.,
(-∞, a)
).
+∞
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.