Find safe travel intervals between planet influences
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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:
- 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`.
Quick Answer: This question evaluates interval arithmetic and line-sweep reasoning for computing complements on the real line, testing competencies in sorting, interval merging, and handling unbounded ranges within the Coding & Algorithms domain and focusing on practical application rather than purely conceptual theory.
You are planning a route along the real x-axis. Each planet is given as a pair (c, r), where c is its center and r is a non-negative radius of gravitational influence. A point x is unsafe if it lies inside at least one planet's influence, meaning |x - c| <= r. So each planet creates an unsafe closed interval [c - r, c + r].
Your task is to return all maximal continuous safe intervals on the real line: regions not covered by any unsafe interval.
Represent each safe interval as a tuple (start, end), where the interval means start < x < end. Because JSON/Python literals do not have a direct infinity literal, use None to represent an unbounded side:
- (None, a) means (-infinity, a)
- (b, None) means (b, +infinity)
- (None, None) means the entire real line
Return the safe intervals in increasing order. Overlapping, nested, and touching unsafe intervals should be treated as one merged unsafe region.
Constraints
- 0 <= len(planets) <= 200000
- -10^9 <= c <= 10^9
- 0 <= r <= 10^9
Examples
Input: []
Expected Output: [(None, None)]
Explanation: With no planets, no point is unsafe, so the entire real line is safe.
Input: [(3, 1), (10, 2)]
Expected Output: [(None, 2), (4, 8), (12, None)]
Explanation: The unsafe intervals are [2, 4] and [8, 12]. Their complement is (-infinity, 2), (4, 8), and (12, +infinity).
Hints
- First convert every planet (c, r) into the unsafe interval [c - r, c + r].
- Sort the unsafe intervals and merge all overlapping or touching ones. The safe intervals are the gaps before, between, and after the merged intervals.