Merge All Overlapping Intervals

medium intervals sorting

Problem

Given a list of intervals [start, end], return their merged form: any two intervals that overlap or touch should be combined into one. Sort by start, then walk through them while keeping a "current" interval. If the next one starts at or before the current end, extend the current end with the larger value; otherwise, push the current and open a new one.

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;
}

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