Merge Overlapping Intervals

Question

The question asks the candidate to write a function that merges overlapping intervals from a given list of intervals.

Codemia · Accepted Answer

To solve the problem of merging overlapping intervals, we can follow these steps:
1. **Sort the intervals** based on the start time. This allows us to easily compare adjacent intervals.
2. **Iterate through the sorted intervals** and compare each interval with the last merged interval. If they overlap, we merge them; otherwise, we add the current interval to the list of merged intervals.

Here is the Python implementation of the solution:
```python
def merge_intervals(intervals):
    if not intervals:
        return []
    # Step 1: Sort the intervals by the start time
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    # Step 2: Iterate through the intervals
    for current in intervals[1:]:
        last_merged = merged[-1]
        # Check if there is an overlap
        if current[0] <= last_merged[1]:
            # Merge the intervals
            last_merged[1] = max(last_merged[1], current[1])
        else:
            # No overlap, add the current interval
            merged.append(current)
    return merged
```
This code sorts the intervals and merges them 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 step runs in O(n), making the overall complexity O(n log n). The space complexity is O(n) for storing the merged intervals.

It is essential to handle edge cases such as:
- An empty list of intervals should return an empty list.
- Intervals that do not overlap at all should return the same list.
- Intervals that completely overlap should return a single merged interval.

To validate the solution, we can run the following test cases:
- Input: `[[1,3],[2,6],[8,10],[15,18]]` → Output: `[[1,6],[8,10],[15,18]]`
- Input: `[[1,4],[4,5]]` → Output: `[[1,5]]`
- Input: `[]` → Output: `[]`
These tests cover typical scenarios, including overlapping intervals, adjacent intervals, and no intervals.

Merge Overlapping Intervals

ByteDance

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

ByteDance Senior SDE, Quality Platform & AI Test Automation 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