Merge Intervals

Question

Given a collection of intervals, merge all overlapping intervals. A frequently asked Meta coding question that tests sorting and greedy algorithm skills.

Codemia · Accepted Answer

The problem requires us to merge overlapping intervals in a collection of intervals. The specific pattern that applies here is the **greedy algorithm** combined with **sorting**. We will sort the intervals based on their start times to facilitate the merging process. Once sorted, we can iterate through the intervals and merge them if they overlap. This approach is efficient and straightforward, as it allows us to handle overlaps in a single pass after sorting.

1. **Sort the Intervals**: Begin by sorting the intervals based on their start times. For example, if our intervals are `[[1,3],[2,6],[8,10],[15,18]]`, sorting will give us `[[1,3],[2,6],[8,10],[15,18]]`.  
2. **Initialize a Result List**: Create an empty list to store the merged intervals.  
3. **Iterate Through the Sorted Intervals**:  
   - Start with the first interval and add it to the result list.  
   - For each subsequent interval, check if it overlaps with the last interval in the result list. An overlap occurs if the start of the current interval is less than or equal to the end of the last interval in the result list.  
   - If they overlap, merge them by updating the end of the last interval in the result list to the maximum of the current interval's end and the last interval's end.  
   - If they do not overlap, simply add the current interval to the result list.  
Example: For `[[1,3],[2,6],[8,10],[15,18]]`, after processing, the merged intervals will be `[[1,6],[8,10],[15,18]]`.

Here is a Python implementation of the approach described:

```python
def merge(intervals):
    # Step 1: Sort the intervals by their start time
    intervals.sort(key=lambda x: x[0])
    
    # Step 2: Initialize the merged list
    merged = []
    
    for interval in intervals:
        # If merged is empty or there is no overlap, add the interval
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # There is an overlap, merge the current interval with the last one in merged
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    return merged
```

This function sorts the intervals and performs the merging in a single pass.

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 process itself is **O(n)**, as we iterate through the list once. Therefore, the overall complexity is dominated by the sorting step. The space complexity is **O(n)** in the worst case when all intervals are non-overlapping, resulting in the merged list containing n intervals.

1. **No Intervals**: If the input is an empty list `[]`, the function should return an empty list as well.  
2. **All Intervals Overlapping**: If all intervals overlap, such as `[[1,4],[2,3],[3,5]]`, the output should be `[[1,5]]`.  
3. **Non-Overlapping Intervals**: For intervals that do not overlap like `[[1,2],[3,4],[5,6]]`, the output should be the same intervals `[[1,2],[3,4],[5,6]]`.  
4. **Single Interval**: A single interval like `[[1,2]]` should return `[[1,2]]`.

Merge Intervals

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Meta 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