Merge Intervals

Problem

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]  
Output: [[1,6],[8,10],[15,18]]  
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]  
Output: [[1,5]]  
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Input

intervals - an array of Interval objects

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

Approach

The easiest way to think about this problem is to understand what the definition of merge is.

If \( A = (2, 5), B = (6, 9) \), then \(A\) does not merge with \(B\).
If \( A = (2, 5), B = (5, 9) \), then \(A\) merges with \(B\) to form \((2, 9)\).
If \( A = (2, 5), B = (3, 9) \), then \(A\) merges with \(B\) to form \((2, 9)\) again.
If \( A = (2, 5), B = (1, 9) \), then \(A\) merges with \(B\) to form \((1, 9)\).
If \( A = (2, 5), B = (1, 1) \), then \(A\) does not merge with \(B\).

What could be said about a merge is the following \(B{end}\) must be greater than \(A{start}\) and \(A{end}\) must be greater than \(B{start}\).

This takes care of what intervals to look for when we consider a merge.

Now, how do we iterate through the input? What we could choose to do is to start a merging sequence, and keep this sequence open as long as the requirements above are met. Once we encounter an interval that is not merge-able with the current sequence, we add the current sequence and start a new sequence, rinsing and repeating this process. In order for this strategy to work, the input array should be sorted by the start value.

Solution

This solution has \(O(n log(n))\) time complexity and constant extra space. A small optimization to this solution involves ditching the use of namedtuple, since creating a new tuple each time we update the current MergeSequence is a bit wasteful. We can instead opt to use two variables that hold integers instead.

    from collections import namedtuple
    MergeSequence = namedtuple('MergeSequence', 'start end')
    def merge(self, intervals: 'List[Interval]') -> 'List[Interval]':
        if len(intervals) == 0:
            return intervals
        res = []

        intervals.sort(key=lambda x: x.start)
        seq = MergeSequence(intervals[0].start, intervals[0].end)

        for i in range(1, len(intervals)):
            start, end = intervals[i].start, intervals[i].end

            # If this interval is mergeable, update current sequence
            if start <= seq.end and end >= seq.start:
                if start < seq.start:
                    seq = MergeSequence(start, seq.end)
                if end > seq.end:
                    seq = MergeSequence(seq.start, end)
            else:
                res.append(Interval(seq.start, seq.end))
                seq = MergeSequence(start, end)

        res.append(Interval(seq.start, seq.end))
        return res

Menu

Problem

Input

Approach

Solution