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`.
Overview: 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.
Community answers
Answer by sourabh.eshaadi
import java.util.*;
public class Solution {
public List> solution(int[][] planets) {
List> result = new ArrayList<>();
if (planets == null || planets.length == 0) {
return result;
}
// Step 1: Generate unsafe intervals [center - radius, center + radius]
List unsafe = new ArrayList<>();
for (int[] planet : planets) {
int c = planet[0];
int r = planet[1];
unsafe.add(new int[]{c - r, c + r});
}
// Step 2: Sort by start point ascending
unsafe.sort(Comparator.comparingInt(a -> a[0]));
// Step 3: Merge overlapping or touching intervals
List merged = new ArrayList<>();
for (int[] interval : unsafe) {
if (merged.isEmpty()) {
merged.add(new int[]{interval[0], interval[1]});
} else {
int[] prev = merged.get(merged.size() - 1);
// Touch or overlap: prev.end >= interval.start
if (prev[1] >= interval[0]) {
prev[1] = Math.max(prev[1], interval[1]);
} else {
merged.add(new int[]{interval[0], interval[1]});
}
}
}
// Step 4: Extract safe gaps between merged intervals
for (int i = 0; i < merged.size() - 1; i++) {
int gapStart = merged.get(i)[1];
int gapEnd = merged.get(i + 1)[0];
// Only add valid non-empty gaps (gapStart < gapEnd)
if (gapStart < gapEnd) {
result.add(Arrays.asList(gapStart, gapEnd));
}
}
return result;
}
}
Answer by sourabh.eshaadi
import java.util.*;
public class Solution {
public List> solution(int[][] planets) {
List> result = new ArrayList<>();
// Case 1: No planets -> Whole real line is safe (-Inf, +Inf)
if (planets == null || planets.length == 0) {
result.add(Arrays.asList(Integer.MIN_VALUE, Integer.MAX_VALUE));
return result;
}
// Step 1: Create unsafe intervals [c - r, c + r]
List unsafe = new ArrayList<>();
for (int[] planet : planets) {
int c = planet[0];
int r = planet[1];
unsafe.add(new int[]{c - r, c + r});
}
// Step 2: Sort by start coordinate ascending
unsafe.sort(Comparator.comparingInt(a -> a[0]));
// Step 3: Merge overlapping or touching intervals
List merged = new ArrayList<>();
for (int[] interval : unsafe) {
if (merged.isEmpty()) {
merged.add(new int[]{interval[0], interval[1]});
} else {
int[] prev = merged.get(merged.size() - 1);
if (prev[1] >= interval[0]) {
prev[1] = Math.max(prev[1], interval[1]);
} else {
merged.add(new int[]{interval[0], interval[1]});
}
}
}
// Step 4: Extract ALL safe gaps including unbounded endpoints
// Leftmost unbounded gap: (-Infinity, first_merged_start)
result.add(Arrays.asList(Integer.MIN_VALUE, merged.get(0)[0]));
// Intermediate safe gaps
for (int i = 0; i < merged.size() - 1; i++) {
int gapStart = merged.get(i)[1];
int gapEnd = merged.get(i + 1)[0];
if (gapStart < gapEnd) {
result.add(Arrays.asList(gapStart, gapEnd));
}
}
// Rightmost unbounded gap: (last_merged_end, +Infinity)
result.add(Arrays.asList(merged.get(merged.size() - 1)[1], Integer.MAX
Answer by bugsbunny
vector> safeZone(vector> planets){
vector> intervals;
for(auto& planet : planets){
intervals.push_back({planet[0]-planet[1], planet[0]+planet[1]}) ;
}
sort(intervals.begin(), intervals.end());
vector> result;
result.push_back({"None"});
for(int i=0;i=intervals[i][0]){
result.back()[1] = to_string(intervals[i][1]);
} else{
result.back().push_back(to_string(intervals[i][0]));
result.push_back({to_string(intervals[i][1])});
}
}
result.back().push_back("None");
return result;
}
Answer by memo
def solution(planets):
if len(planets) == 0:
return [(None, None)]
nums = []
for c,r in planets:
nums.append([c-r, c+r])
nums.sort()
ans = [[None, nums[0][0]]]
last_end = nums[0][1]
for start, end in nums[1:]:
if start > last_end:
ans.append([last_end, start])
last_end = max(last_end, end)
ans.append([last_end, None])
return ans