Find shortest distance in interval list

Question

Given a list of intervals, each defined by a start and end point, write a function to find the shortest distance between any two non-overlapping intervals. The function should take a list of intervals as input and return the minimum distance as an integer. If all intervals overlap, return 0.

Codemia · Accepted Answer

To solve the problem of finding the shortest distance between non-overlapping intervals, we can utilize a two-pointer technique. This method is applicable here because we can efficiently traverse the list of intervals while maintaining the current minimum distance between intervals. The intervals need to be sorted first to ensure that we can easily check for overlaps and compute distances. This approach allows us to systematically compare the intervals while avoiding unnecessary calculations.

1. **Sort the intervals**: Start by sorting the list of intervals based on their start points. This will help us efficiently check for overlaps and calculate distances.
   
   Example: Given intervals `[(1, 3), (2, 4), (5, 7), (8, 10)]`, after sorting, they remain the same.

2. **Initialize pointers**: Use two pointers, `i` and `j`, where `i` points to the current interval being considered and `j` is used to compare against the next interval.

3. **Iterate through intervals**: For each interval `i`, check if it overlaps with interval `j`. If they overlap, move `i` forward. If they do not overlap, calculate the distance between the end of interval `i` and the start of interval `j`. Keep track of the minimum distance encountered.

Example: For intervals `[(1, 3), (2, 4), (5, 7), (8, 10)]`, the distance between `(3, 5)` is `2`, which is a candidate for the minimum distance.

4. **Return result**: If no non-overlapping intervals are found, return 0; otherwise, return the minimum distance.

Here is the Python code implementing the above approach:

```python
def find_min_distance(intervals):
    # Step 1: Sort intervals based on start points
    intervals.sort(key=lambda x: x[0])
    min_distance = float('inf')
    n = len(intervals)

# Step 2: Two pointers to iterate through intervals
    i, j = 0, 1

while j < n:
        # Step 3: Check for overlaps
        if intervals[i][1] >= intervals[j][0]:
            # If they overlap, move `i` to the next interval
            i += 1
            if i == j:  # Ensure `i` and `j` do not point to the same interval
                j += 1
        else:
            # Calculate distance between non-overlapping intervals
            distance = intervals[j][0] - intervals[i][1]
            min_distance = min(min_distance, distance)
            j += 1

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

In this code, we maintain a sorted list of intervals and calculate the minimum distance iteratively.

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 pass through the intervals using two pointers is O(n). Therefore, the overall complexity is dominated by the sorting, resulting in O(n log n).

The space complexity is O(1) if we consider sorting in place, as we do not use any additional data structures that scale with input size.

1. **All intervals overlap**: For example, intervals `[(1, 5), (2, 3), (4, 6)]` should return 0 since they all overlap. 
   
2. **Non-overlapping intervals**: For intervals `[(1, 2), (3, 4), (5, 6)]`, the expected output is 1, as the shortest distance is between the end of the first interval and the start of the second.
   
3. **Single interval**: If the input is `[(1, 3)]`, the function should return 0 since there are no pairs of intervals to compare. 
   
4. **Empty list**: An empty list of intervals should also return 0, as there are no intervals to measure distances between.

Find shortest distance in interval list

Bloomberg

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

Bloomberg Software 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