DFS on interval list

Question

Given a list of intervals, implement a Depth-First Search (DFS) algorithm to explore all possible combinations of overlapping intervals and return a list of merged intervals that cover all the ranges. The input will be a list of intervals represented as pairs of integers, and the output should be a list of merged intervals in the same format. Ensure that the solution efficiently handles cases with overlapping and contiguous intervals.

Codemia · Accepted Answer

The problem at hand requires merging overlapping intervals, which is a classic example of interval management typically solved using sorting followed by a linear scan. However, since we are asked to implement a DFS algorithm, we can treat this as a graph traversal problem where each interval can be seen as a node and overlapping intervals as edges connecting those nodes. The DFS will help us explore all possible combinations of overlapping intervals. This approach applies here because it effectively allows us to explore all paths (i.e., all combinations of overlapping intervals) and ensures we can merge them appropriately.

1. **Sort the Intervals**: First, sort the intervals based on their start time. This helps in easily identifying overlapping intervals. For example, given intervals `[[1, 3], [2, 6], [8, 10], [15, 18]]`, after sorting, they remain the same since they are already sorted.
2. **DFS Implementation**: Create a recursive DFS function that will attempt to merge intervals. Start from the first interval and try to merge it with any overlapping intervals found in the list. Use a visited set to avoid re-processing intervals.
3. **Merging Logic**: If the current interval overlaps with the next interval (i.e., the start of the next interval is less than or equal to the end of the current interval), update the end of the current interval to the maximum of the two ends. Continue this until all intervals have been processed. For example, merging `[1, 3]` and `[2, 6]` results in `[1, 6]`. 
4. **Collect Results**: After processing all intervals, collect the merged intervals into a result list.

Here is a Python implementation of the described approach:
```python
def merge_intervals(intervals):
    if not intervals:
        return []
    
    # Step 1: Sort intervals by the start time
    intervals.sort(key=lambda x: x[0])
    merged = []
    
    # Step 2: Initialize the first interval
    current_start, current_end = intervals[0]
    
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        # Step 3: Check for overlap
        if start <= current_end:
            current_end = max(current_end, end)
        else:
            merged.append([current_start, current_end])
            current_start, current_end = start, end
    
    # Step 4: Append the last merged interval
    merged.append([current_start, current_end])
    return merged
```
This code sorts the intervals and then merges them in a single pass through the sorted list.

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of intervals. The merging step runs in O(n) time, leading to an overall complexity of O(n log n). The space complexity is O(n) in the worst case when all intervals are non-overlapping and need to be stored in the result list.

1. **Empty Input**: If the input list is empty, the output should also be an empty list. 
2. **Single Interval**: If there's only one interval, it should return the same interval. 
3. **All Intervals Overlap**: If all intervals overlap, the function should return a single merged interval that covers the entire range. For example, `[[1, 4], [2, 3], [3, 5]]` should return `[[1, 5]]`. 
4. **Non-Overlapping Intervals**: If all intervals do not overlap, the output should be the same as the input. For example, `[[1, 2], [3, 4]]` should return `[[1, 2], [3, 4]]`.

DFS on interval list

Dropbox

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

Dropbox 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