0056 Merge Intervals

0056 Merge Intervals#

Problem#

Given an array of intervals where `intervals[i] = [starti, endi]``, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Examples#

Example 1:

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

Example 2:

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

Constraint#

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

Analysis#

  • sort the intervals based on the start point

  • traverse the intervals, and compare the end point of the previous interval and the current interval

    • if the end point of the previous interval is greater than the end point of the current interval, then the current interval is covered by the previous interval

Solution#

def mergeInterval(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

# test 
intervals = [[1,3],[2,6],[8,10],[15,18]]
mergeInterval(intervals)

[[1, 6], [8, 10], [15, 18]]
Contents