MediumBlind75ArraySort

Merge Intervals

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

Examples

Input
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]

Intervals [1,3] and [2,6] overlap, so they are merged into [1,6].

Input
intervals = [[1,4],[4,5]]
Output
[[1,5]]

Intervals [1,4] and [4,5] are considered overlapping and are merged into [1,5].

Constraints

  • •1 <= intervals.length <= 10^4
  • •intervals[i].length == 2
  • •0 <= starti <= endi <= 10^4

Approaches

Compare each interval with all others and merge overlaps.

CodeT: O(n^2) | S: O(n)
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        merged_flag = False
        for m in merged:
            if m[1] >= interval[0] and m[0] <= interval[1]:
                m[0] = min(m[0], interval[0])
                m[1] = max(m[1], interval[1])
                merged_flag = True
                break
        if not merged_flag:
            merged.append(interval)
    return merged

Sort by start time, then merge overlapping intervals.

CodeT: O(n log n) | S: O(n)
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for interval in intervals[1:]:
        if merged[-1][1] >= interval[0]:
            merged[-1][1] = max(merged[-1][1], interval[1])
        else:
            merged.append(interval)
    return merged

Same approach with cleaner implementation.

Diagram

intervals = [[1,3],[2,6],[8,10],[15,18]] Sorted: [[1,3],[2,6],[8,10],[15,18]] [1,3] and [2,6] overlap -> [1,6] [1,6] and [8,10] no overlap -> add [8,10] [8,10] and [15,18] no overlap -> add [15,18] Result: [[1,6],[8,10],[15,18]]
CodeT: O(n log n) | S: O(n)
def merge(intervals):
    if not intervals:
        return []
    intervals.sort(key=lambda x: x[0])
    result = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result

Complexity Comparison

Brute Force - Compare All
T: O(n^2)S: O(n)

Compare each interval with all others and merge overlaps.

Sort and Merge
T: O(n log n)S: O(n)

Sort by start time, then merge overlapping intervals.

Optimized Sort and Merge
T: O(n log n)S: O(n)

Same approach with cleaner implementation.

Common Mistakes

Not sorting intervals first

Forgetting to check if the current interval overlaps with the last merged one

Using extra space when the result can be stored in the original array

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems