Merge K Sorted graphs

Question

Given three sorted interval lists, merge them into a single sorted result.

Codemia · Accepted Answer

This problem involves merging three sorted interval lists into a single sorted result. The underlying pattern here is the **merge process of the merge sort algorithm**. Since each list is already sorted, we can efficiently merge them using a two-pointer technique, iterating through each of the lists simultaneously. This approach is optimal because it allows us to maintain the order of elements while merging, taking advantage of the initial sorted property of the lists.

1. Initialize three pointers, one for each of the three interval lists. 
2. Create an empty result list to store the merged intervals.
3. Compare the intervals pointed by the three pointers:
   - Select the smallest interval among the three and append it to the result list.
   - Move the pointer of the list from which the interval was taken.
4. Repeat steps 3 until all intervals from all lists have been merged.
5. If any intervals remain in any of the lists after the main loop, append them to the result list.

**Example:**
Given intervals: 
- List 1: [(1, 3), (5, 6)]
- List 2: [(2, 4), (7, 8)]
- List 3: [(0, 1), (3, 5)]

The merging process would compare:
- Start with pointers at (1, 3), (2, 4), and (0, 1).
- Append (0, 1) to result. Move pointer 3 to (1, 3).
- Compare (1, 3), (2, 4), (1, 3). Append (1, 3). Move pointer 1 to (5, 6).
- Continue until all intervals are processed.

```python
from typing import List, Tuple

def merge_k_sorted_intervals(list1: List[Tuple[int, int]], list2: List[Tuple[int, int]], list3: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
    merged_intervals = []
    i, j, k = 0, 0, 0
    total_intervals = len(list1) + len(list2) + len(list3)

while len(merged_intervals) < total_intervals:
        min_interval = None
        if i < len(list1) and (min_interval is None or list1[i] < min_interval):
            min_interval = list1[i]
        if j < len(list2) and (min_interval is None or list2[j] < min_interval):
            min_interval = list2[j]
        if k < len(list3) and (min_interval is None or list3[k] < min_interval):
            min_interval = list3[k]

merged_intervals.append(min_interval)
        if i < len(list1) and min_interval == list1[i]:
            i += 1
        elif j < len(list2) and min_interval == list2[j]:
            j += 1
        elif k < len(list3) and min_interval == list3[k]:
            k += 1

return merged_intervals
```

The time complexity of this algorithm is **O(n)**, where **n** is the total number of intervals across all three lists. This is because we traverse each list exactly once, making a constant number of comparisons at each step. The space complexity is also **O(n)** for storing the merged intervals in the output list. Given that we are using three pointers, the additional space used for them is constant, which does not affect the overall space complexity.

1. **Empty Lists:** If all input lists are empty, the output should also be an empty list.
2. **Overlapping Intervals:** If intervals overlap within the lists, the algorithm should still correctly merge them into a single sorted list without duplicates.
3. **Single Interval Lists:** If any of the lists contain only one interval, it should be handled correctly and merged with the others.
4. **Extreme Values:** Consider cases where intervals might contain negative numbers or very large numbers, ensuring that they are compared correctly.

Merge K Sorted graphs

Robinhood

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

Robinhood 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