Merge Three Sorted interval lists

Question

Given three sorted lists of intervals, merge them into a single sorted list of intervals. The output should contain the merged intervals, ensuring that overlapping intervals are combined into one. The input will consist of three lists, each containing intervals represented as pairs of integers, and the output should be a single list of merged intervals sorted by their start times.

Codemia · Accepted Answer

This problem can be approached using the 'merge intervals' technique, which is a common problem pattern when dealing with sorted interval lists. Given that we have three separate sorted lists of intervals, we can merge them efficiently by first combining all intervals into a single list and then applying the merge interval logic to combine overlapping intervals. The key here is that since the input lists are already sorted, we can maintain this order while merging.

1. **Combine Intervals**: Start by concatenating the three lists of intervals into a single list.
2. **Sorting**: Although the individual lists are sorted, we need to ensure the combined list is sorted as well. This can be done using the built-in sorting function based on the start of the intervals.
3. **Merge Overlapping Intervals**: Initialize an empty list to hold the merged intervals. Iterate through the sorted list. For each interval, check if it overlaps with the last added interval in the merged list: 
   - If it overlaps (i.e., the start of the current interval is less than or equal to the end of the last merged interval), merge them by updating the end of the last merged interval to the maximum of the two ends.
   - If it does not overlap, simply append the current interval to the merged list.

**Example**: Given intervals `[[1, 3], [2, 4], [5, 7], [6, 8]]`, after merging:
- Combine: `[[1, 3], [2, 4], [5, 7], [6, 8]]`
- After sorting: `[[1, 3], [2, 4], [5, 7], [6, 8]]`
- Merged result: `[[1, 4], [5, 8]]`.

Here is a Python implementation of the solution:

```python
def merge_intervals(intervals1, intervals2, intervals3):
    # Step 1: Combine all intervals
    all_intervals = intervals1 + intervals2 + intervals3

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

# Step 3: Merge intervals
    merged_intervals = []
    for interval in all_intervals:
        if not merged_intervals:
            merged_intervals.append(interval)
        else:
            last_merged = merged_intervals[-1]
            if last_merged[1] >= interval[0]:  # Overlapping intervals
                last_merged[1] = max(last_merged[1], interval[1])  # Merge
            else:
                merged_intervals.append(interval)  # No overlap

return merged_intervals
```

This function takes three lists of intervals, merges them into one sorted list, and returns the merged intervals.

The time complexity of this solution is O(N log N), where N is the total number of intervals across all three lists. This is primarily due to the sorting step. The merging process itself is O(N) as we simply traverse the sorted list once. The space complexity is O(N) as well, since we store the merged intervals in a new list.

1. **Empty Input**: If all three lists are empty, the function should return an empty list.
2. **Single Interval**: If one list contains a single interval and the others are empty, the output should be that single interval.
3. **No Overlapping Intervals**: If all intervals are non-overlapping, the output should simply return all intervals as they are.
4. **Completely Overlapping Intervals**: If all intervals are the same, the result should be just one interval.

These edge cases ensure that the function handles a variety of inputs robustly.

Merge Three Sorted interval lists

Adobe

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

Adobe 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