Merge Overlapping Intervals

Problem

You have some overlapping closed intervals and you want to merge them. What is the algorithm for this?

Solution

Here are some examples with input and output:

Input1: Intervals = [[1, 3], [2, 4], [6, 8], [9, 10]]

Output1: [[1, 4], [6, 8], [9, 10]]


Input2: Intervals = [[6, 8], [1, 9], [2, 4], [4, 7]]

Output2: [[1, 9]]

And the algorithm:

def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
    # Sort the array on the basis of start values of intervals.
    intervals.sort()
    stack = []
    # insert first interval into stack
    stack.append(intervals[0])
    for curr in intervals[1:]:
        # Check for overlapping interval,
        # if interval overlap
        if stack[-1][0] <= curr[0] <= stack[-1][-1]:
            stack[-1][-1] = max(stack[-1][-1], curr[-1])
        else:
            stack.append(curr)
        #
    #
    return stack

Links

• https://www.geeksforgeeks.org/merging-intervals/ (found here)