Solutions

1. Sorting

O(nlogn) time | O(n) space

Intuition

If we sort the intervals by their start first, we can use one loop and merge them one by one as every interval that overlaps another one comes right after it.

At each iteration the interval either stretches the previous one or becomes a new one.

Algorithm

Create an empty array result.
Sort the intervals by their start.
Iterate through the loop from the first interval to the last interval.
- If the interval starts at or before the end of the last interval of result, replace that end with the greater of the two ends.
- Otherwise add the interval to result.
Return the result.

[1, 3]

[2, 6]

[8, 10]

[15, 18]

merged

05101520

take [1, 3]

1 / 5

Code

def merge(intervals: list[list[int]]) -> list[list[int]]:
    result = []
    for start, end in sorted(intervals):
        if result and start <= result[-1][1]:
            result[-1][1] = max(result[-1][1], end)
        else:
            result.append([start, end])
    return result

/**
 * @param {number[][]} intervals
 * @returns {number[][]}
 */
var merge = function (intervals) {
  const result = []
  for (const [start, end] of [...intervals].sort((a, b) => a[0] - b[0])) {
    const last = result[result.length - 1]
    if (last && start <= last[1]) last[1] = Math.max(last[1], end)
    else result.push([start, end])
  }
  return result
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0]));
        List<int[]> result = new ArrayList<>();
        for (int[] span : sorted) {
            int[] last = result.isEmpty() ? null : result.get(result.size() - 1);
            if (last != null && span[0] <= last[1]) last[1] = Math.max(last[1], span[1]);
            else result.add(new int[] { span[0], span[1] });
        }
        return result.toArray(new int[0][]);
    }
}