Compute the Union of Two Sorted Interval Lists

Question

The question asks the candidate to compute the union of two sorted lists of intervals, merging any overlapping intervals into a single interval.

Codemia · Accepted Answer

To solve the problem of merging two sorted interval lists, we can use a two-pointer technique. We will iterate through both lists simultaneously, comparing the current intervals and merging them when they overlap. This approach ensures that we efficiently traverse both lists without unnecessary comparisons.

1. Initialize two pointers, `i` and `j`, to the start of both interval lists.
2. Create an empty list `merged` to store the resulting merged intervals.
3. While both pointers are within the bounds of their respective lists:
   - Compare the current intervals from both lists.
   - If they overlap, merge them and move the pointer of the interval that ends first.
   - If they do not overlap, add the interval that ends first to the `merged` list and move the corresponding pointer.
4. After the loop, add any remaining intervals from both lists to `merged`.

The time complexity of this algorithm is O(n + m), where n and m are the lengths of the two interval lists. This is because we traverse each list once. The space complexity is O(k), where k is the number of merged intervals, as we store the results in a new list.

```python
def merge_intervals(intervals1, intervals2):
    merged = []
    i, j = 0, 0

while i < len(intervals1) and j < len(intervals2):
        start1, end1 = intervals1[i]
        start2, end2 = intervals2[j]

if end1 < start2:
            merged.append(intervals1[i])
            i += 1
        elif end2 < start1:
            merged.append(intervals2[j])
            j += 1
        else:
            merged.append([min(start1, start2), max(end1, end2)])
            if end1 < end2:
                i += 1
            else:
                j += 1

# Add remaining intervals
    while i < len(intervals1):
        merged.append(intervals1[i])
        i += 1
    while j < len(intervals2):
        merged.append(intervals2[j])
        j += 1

return merged
```

Make sure to consider edge cases such as:
- One or both of the interval lists being empty.
- Intervals that are completely overlapping.
- Intervals that touch but do not overlap. These scenarios should be handled gracefully in the implementation.

Compute the Union of Two Sorted Interval Lists

Google

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

Google 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