Find shortest distance in interval list

Question

Given a list of intervals, write a function to find the shortest distance between any two intervals that do not overlap. The function should take a list of intervals as input, where each interval is represented as a pair of integers [start, end], and return the minimum distance as an integer. If all intervals overlap, return -1.

Codemia · Accepted Answer

To find the shortest distance between non-overlapping intervals, we can leverage sorting and a linear scan. The two-pointer technique applies here since we can keep track of two intervals—one for the current interval being examined and another for the next interval that follows. By sorting the intervals based on their starting points, we can efficiently identify non-overlapping pairs and calculate their distances.

1. **Sort the Intervals**: Begin by sorting the list of intervals based on their start times. This allows us to compare only consecutive intervals for potential overlaps and distances.

2. **Initialize Variables**: Create a variable `min_distance` and set it to infinity to track the minimum distance found. Also, maintain a variable `prev_end` initialized to the end of the first interval.

3. **Iterate Through Intervals**: Loop through the sorted intervals starting from the second interval. For each interval:
   - Check if the current interval's start time is greater than the previous interval's end time (`prev_end`). If so, calculate the distance as `current_interval.start - prev_end`, and update `min_distance` if this distance is smaller.
   - Update `prev_end` to the maximum of `prev_end` and the current interval's end.

4. **Check Result**: After the loop, if `min_distance` is still infinity, it implies that there were no non-overlapping intervals, so return -1. Otherwise, return `min_distance`.

```python
from typing import List

def find_shortest_distance(intervals: List[List[int]]) -> int:
    if not intervals:
        return -1

# Step 1: Sort intervals by the start time
    intervals.sort(key=lambda x: x[0])

min_distance = float('inf')
    prev_end = intervals[0][1]

# Step 2: Iterate through intervals
    for i in range(1, len(intervals)):
        current_start = intervals[i][0]
        current_end = intervals[i][1]

# Check for non-overlapping intervals
        if current_start > prev_end:
            distance = current_start - prev_end
            min_distance = min(min_distance, distance)

# Update prev_end
        prev_end = max(prev_end, current_end)

return min_distance if min_distance != float('inf') else -1
```

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of intervals. The subsequent linear scan through the intervals runs in O(n). Thus, the overall time complexity is O(n log n). The space complexity is O(1) as we are only using a fixed amount of extra space for variables, aside from the input list.

1. **All Intervals Overlapping**: If all the intervals overlap (e.g., [[1, 5], [2, 6], [3, 7]]), the function should return -1, indicating no non-overlapping intervals exist.

2. **Single Interval**: If there's only one interval (e.g., [[1, 3]]), it should return -1 since there are no pairs to compare.

3. **Empty List**: If the input list is empty, the function should also return -1, as there are no intervals to process.

4. **Intervals with Same Start and End**: Intervals like [[1, 2], [2, 3]] should be handled correctly as they are non-overlapping but touch at a point.

Find shortest distance in interval list

Confluent

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Confluent Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string