Merge Intervals

medium intervals sorting

Problem

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

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

Output[[1,6],[8,10],[15,18]]

[1,3] and [2,6] overlap → [1,6]; the rest stand alone.

intervals (semicolon-separated, "a,b")

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = []
    for s, e in intervals:
        if out and out[-1][1] >= s:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

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

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

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b){ return a[0] < b[0]; });
    vector<vector<int>> out;
    for (auto& iv : intervals) {
        if (!out.empty() && out.back()[1] >= iv[0]) {
            out.back()[1] = max(out.back()[1], iv[1]);
        } else {
            out.push_back(iv);
        }
    }
    return out;
}

Explanation

Overlapping intervals can only sit next to each other once everything is in order, so we first sort by start. Then a single sweep merges anything that touches.

We build an output list out. For each interval [s, e], if the last interval in out reaches into it (out[-1][1] >= s), they overlap, so we extend that last interval's end with max(out[-1][1], e). Otherwise there is a gap, so we start a fresh interval.

Using max for the end is important, because the current interval might end earlier than the one we are extending and we must not shrink it.

Example: [[1,3],[2,6],[8,10],[15,18]]. [1,3] and [2,6] overlap into [1,6]; [8,10] and [15,18] stand alone, giving [[1,6],[8,10],[15,18]].

Because the list is sorted, checking only the most recent output interval is enough to catch every merge.

Time: O(n log n) Space: O(n)