Merge Intervals

MediumArray Sorting Intervals

A calendar app shows each person's day as a set of busy blocks. It receives the raw meetings as closed intervals intervals[i] = [start, end] with start <= end, in no particular order, and must combine every group of overlapping meetings into a single busy block. Meetings that merely touch, such as [9,10] and [10,11], merge as well.

Return the merged blocks sorted by start time, which makes the answer unique.

Example 1

Input: intervals = [[9,12],[1,3],[11,14],[3,5]]
Output: [[1,5],[9,14]]

Explanation: [1,3] and [3,5] touch at 3, and [9,12] overlaps [11,14], so two busy blocks remain.

Example 2

Input: intervals = [[3,10],[4,5],[7,8]]
Output: [[3,10]]

Explanation: Both shorter meetings sit entirely inside [3,10].

Example 3

Input: intervals = [[13,15],[0,2],[6,8]]
Output: [[0,2],[6,8],[13,15]]

Explanation: Nothing overlaps, so the blocks only need sorting.

Constraints

There are between 1 and 10^4 meetings.
Each meeting is a pair of integers between 0 and 10^4, and its start is never after its end.

Follow-up: If meetings are booked one at a time and the busy blocks must stay merged after every booking, 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