60. Merge Intervals

MediumArray Sorting Intervals

You are given an array of closed intervals intervals, where intervals[i] = [start, end] and start <= end. The input is not necessarily sorted.

Merge every group of overlapping intervals into one interval and return the result. Intervals that merely touch, such as [1,2] and [2,3], also count as overlapping.

Return the merged intervals sorted by start (the answer is then unique).

Example 1

Input: intervals = [[1,4],[2,5],[7,9]]
Output: [[1,5],[7,9]]

Explanation: [1,4] and [2,5] overlap on [2,4], so they become [1,5].

Example 2

Input: intervals = [[6,8],[1,3],[2,4]]
Output: [[1,4],[6,8]]

Explanation: The input order does not matter; the output is sorted by start.

Example 3

Input: intervals = [[1,2],[2,3]]
Output: [[1,3]]

Explanation: Touching endpoints merge.

Constraints

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start <= end <= 10^4

Follow-up: If the intervals arrive one at a time and you must keep the merged set up to date, what data structure would you use?

💡 Hint 1

If the intervals were sorted by start, which intervals could possibly overlap the current one?

💡 Hint 2

After sorting, walk the list keeping the last merged interval. The next interval either starts at or before its end (extend it) or after its end (start a new one).

💡 Hint 3

When extending, the new end is the max of the two ends, since one interval may sit completely inside another.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Sort the intervals by start. Then any interval that overlaps the most recent merged block must start at or before that block's end. Walk the sorted list: if start <= last[1], extend last[1] = max(last[1], end); otherwise push a new block. Because blocks are created in increasing start order, the output is already sorted.

Time O(n log n)Space O(n) for the output (plus the sort)

function merge(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [start, end] of sorted) {
    const last = out[out.length - 1];
    if (last && start <= last[1]) last[1] = Math.max(last[1], end);
    else out.push([start, end]);
  }
  return out;
}

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

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
function merge(intervals) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit