Merge K Sorted interval lists

Question

Given three sorted grids, merge them into a single sorted result.

Codemia · Accepted Answer

The problem involves merging multiple sorted lists of intervals into a single sorted list. The key observation is that these lists are sorted individually, which suggests the use of a merging strategy similar to the merge step in the Merge Sort algorithm. We can utilize a min-heap (or priority queue) to efficiently track the smallest intervals from each list to merge them in sorted order. The challenge lies in maintaining the sorted order while merging potentially overlapping intervals from different lists.

1. **Initialize a Min-Heap**: Start by creating a min-heap to keep track of the current intervals from each list. Each entry in the heap will store the interval along with its originating list index.  
2. **Insert First Interval From Each List**: Push the first interval from each of the K lists into the min-heap.  
3. **Merge Intervals**: Extract the smallest interval from the heap and add it to the result list. Check if this interval overlaps with the last added interval in the result. If it overlaps, merge them (by updating the end of the last added interval). If not, simply add the new interval to the result.  
4. **Continue Until All Intervals Are Processed**: If the extracted interval has a next interval in the same list, push that next interval into the heap. Repeat until the heap is empty.  
5. **Return Result**: The result list will contain the merged intervals in sorted order.

**Example**: Given three sorted lists: [[1,3], [2,6], [8,10], [15,18]], [[1,4], [4,5]], [[2,3], [6,8]], the process would involve pushing the first intervals into the heap, merging overlapping intervals, and finally producing [[1, 6], [8, 10], [15, 18]].

```python
import heapq

def merge_k_sorted_intervals(intervals):
    min_heap = []
    result = []

# Insert the first interval from each list into the min-heap
    for i, lst in enumerate(intervals):
        if lst:
            heapq.heappush(min_heap, (lst[0][0], lst[0][1], i, 0))  # (start, end, list index, index in list)

while min_heap:
        start, end, list_index, interval_index = heapq.heappop(min_heap)
        # If result is empty or no overlap, add the new interval
        if not result or result[-1][1] < start:
            result.append([start, end])
        else:
            # Overlapping intervals, merge them
            result[-1][1] = max(result[-1][1], end)

# If there's a next interval in the same list, push it into the heap
        if interval_index + 1 < len(intervals[list_index]):
            next_interval = intervals[list_index][interval_index + 1]
            heapq.heappush(min_heap, (next_interval[0], next_interval[1], list_index, interval_index + 1))

return result
```
This code initializes a min-heap, processes intervals to merge them, and maintains the sorted order throughout.

The time complexity of this approach is O(N log K), where N is the total number of intervals across all K lists. Each insertion and extraction operation from the min-heap takes O(log K) time, and we perform these operations for each interval. The space complexity is O(K) due to the storage of the min-heap which holds at most K intervals at any time.

1. **Empty Input**: If all three lists are empty (e.g., []), the function should return an empty list.  
2. **Single List**: If only one list contains intervals (e.g., [[1,3], [2,4]]), the function should correctly merge overlapping intervals and return [[1, 4]].  
3. **Non-Overlapping Intervals**: If intervals do not overlap at all across lists (e.g., [[1,2], [3,4], [5,6]]), the function should return them as is.  
4. **Single Interval**: If the lists contain only one interval each (e.g., [[1,2], [3,4], [5,6]]), the function should return [[1,2], [3,4], [5,6]].

Merge K Sorted interval lists

Meta

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

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