noodleProblems/
Merge Intervals
#13

Merge Intervals

AlgorithmmediumArraySorting
New York Times

Given a list of intervals where each intervals[i] = [start, end], merge every pair of overlapping intervals and return the resulting non-overlapping intervals.

Two intervals overlap when one starts at or before the other ends (touching endpoints such as [1, 4] and [4, 5] count as overlapping). Return the merged intervals **sorted in ascending order of start**.

Example cases

  • overlapping pair
    in intervals =
    13
    26
    810
    1518
    out [[1,6],[8,10],[15,18]]
    [1,3] and [2,6] overlap, so they merge into [1,6]; the rest stay separate.
  • touching endpoints
    in intervals =
    14
    45
    out [[1,5]]
    They share the endpoint 4, which counts as overlapping.
  • already disjoint
    in intervals =
    12
    34
    out [[1,2],[3,4]]

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start <= end <= 10^4
Saved
intervals =
[[1,3],[2,6],[8,10],[15,18]]