Merge Intervals Follow-up

Problem

Given two sorted interval lists with no overlapping intervals inside each list, merge them into one sorted non-overlapping list.

Example

Input:
intervals1 = [[1,3],[6,9]]
intervals2 = [[2,5],[10,12]]

Output:
[[1,5],[6,9],[10,12]]
    

Approach

First merge the two sorted interval lists using two pointers. Then perform the standard merge-interval process on the combined sorted list.

Complexity

Solution

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

    while i < len(intervals1) and j < len(intervals2):
        if intervals1[i][0] < intervals2[j][0]:
            merged.append(intervals1[i])
            i += 1
        else:
            merged.append(intervals2[j])
            j += 1

    merged.extend(intervals1[i:])
    merged.extend(intervals2[j:])

    result = []

    for interval in merged:
        if not result or result[-1][1] < interval[0]:
            result.append(interval)
        else:
            result[-1][1] = max(result[-1][1], interval[1])

    return result
    

Related Topics