Intervals

Merge Intervals

medium

DESCRIPTION (inspired by Leetcode.com)

Write a function to consolidate overlapping intervals within a given array intervals, where each interval intervals[i] consists of a start time starti and an end time endi.

Two intervals are considered overlapping if they share any common time, including if one ends exactly when another begins (e.g., [1,4] and [4,5] overlap and should be merged into [1,5]).

The function should return an array of the merged intervals so that no two intervals overlap and all the intervals collectively cover all the time ranges in the original input.

Input:

intervals = [[3,5],[1,4],[7,9],[6,8]]

Output:

[[1,5],[6,9]]

Explanation: The intervals [3,5] and [1,4] overlap and are merged into [1,5]. Similarly, [7,9] and [6,8] overlap and are merged into [6,9].

Code Editor

Run your code to see results here

Have suggestions or found something wrong?

Explanation

Since this question involves merging intervals that overlap, we want to first sort the intervals by their start time. This allows us to easily check if an interval overlaps with the one before it. Then we create a new array to store the merged intervals.

We iterate through the sorted intervals and check if the current interval overlaps with the last interval in the merged array. If it does, we merge the intervals by updating the end time of the last interval in the merged array to be the maximum of the end times of the current interval and the last interval in the merged array (i.e. max(merged[-1][1], current[1])).

Note the first interval can always be added directly to the merged array.

Visualization


def mergeIntervals(intervals):
    sortedIntervals = sorted(intervals, key=lambda x: x[0])
    merged = []
        
    for interval in sortedIntervals:
        if not merged or interval[0] > merged[-1][1]:
            merged.append(interval)
        else:
            merged[-1][1] = max(interval[1], merged[-1][1])
    return merged

intervals[1]

0 / 1

Merging an overlapping interval

If it doesn't, we add the current interval directly to the merged array.

Visualization


def mergeIntervals(intervals):
    sortedIntervals = sorted(intervals, key=lambda x: x[0])
    merged = []
        
    for interval in sortedIntervals:
        if not merged or interval[0] > merged[-1][1]:
            merged.append(interval)
        else:
            merged[-1][1] = max(interval[1], merged[-1][1])
    return merged

intervals[2]

0 / 1

Adding an interval that does not overlap

What is the time complexity of this solution?

O(V + E)

O(n)

O(n³)

O(n * logn)

Solution

Try these examples:

Visualization


def mergeIntervals(intervals):
    sortedIntervals = sorted(intervals, key=lambda x: x[0])
    merged = []
        
    for interval in sortedIntervals:
        if not merged or interval[0] > merged[-1][1]:
            merged.append(interval)
        else:
            merged[-1][1] = max(interval[1], merged[-1][1])
    return merged

merge intervals

0 / 10

Mark as read

Next: Employee Free Time