Beyond Big O

Merge overlapping intervals

Merge overlapping intervals

Medium

Your task

  • Combine overlapping intervals and return their union, sorted by start.
  • Each interval is closed: both endpoints count.
  • For example, [1,3] and [3,5] touch and must merge into [1,5].

Required API

  • MergeIntervals
    func MergeIntervals(intervals [][2]int) [][2]int

Behavior

  • A gap still separates intervals, even between adjacent integers: [1,2] and [3,4] remain separate.
  • Zero-length intervals and duplicate intervals are valid.
  • Empty input returns an empty array.
  • Leave every input interval and the outer array unchanged.
  • Separate calls must not share state.
  • Aim for O(n log n) time and O(n) extra space using only the standard library.
  • Explain why a nested interval must never shrink the current merged end.

Constraints

  • The input is valid: 0–250 intervals in any order.
  • Each interval contains exactly two integers between -100,000 and 100,000 inclusive, with start <= end.
  • Reversed intervals are outside the input contract.
Notes and example notation

Examples use {"intervals": [[start, end], ...]}.

Examples

The runner calls your functions directly; you do not need to parse JSON.

Example 1 · empty

Arguments
intervals
[]
Expected return
[]
Test data
Input
{"intervals":[]}
Expected output
[]

Example 2 · overlap

Arguments
intervals
[
  [
    5,
    8
  ],
  [
    1,
    4
  ],
  [
    3,
    6
  ]
]
Expected return
[
  [
    1,
    8
  ]
]
Test data
Input
{"intervals":[[5,8],[1,4],[3,6]]}
Expected output
[[1,8]]

Example 3 · touching

Arguments
intervals
[
  [
    1,
    3
  ],
  [
    3,
    5
  ],
  [
    8,
    10
  ]
]
Expected return
[
  [
    1,
    5
  ],
  [
    8,
    10
  ]
]
Test data
Input
{"intervals":[[1,3],[3,5],[8,10]]}
Expected output
[[1,5],[8,10]]

Example 4 · nested

Arguments
intervals
[
  [
    1,
    10
  ],
  [
    2,
    3
  ],
  [
    4,
    8
  ]
]
Expected return
[
  [
    1,
    10
  ]
]
Test data
Input
{"intervals":[[1,10],[2,3],[4,8]]}
Expected output
[[1,10]]
Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…