Combine Intervals

Given a list of [start, end] intervals, merge all overlapping (or touching) intervals and return the result sorted by start.

combineIntervals(intervals)

Two intervals overlap if one's start is <= the other's end.

Input format: intervals as start,end pairs separated by spaces. Output the merged intervals the same way (e.g. 1,6 8,10).

Examples

[1,3] [2,6] [8,10] [15,18]   // → [1,6] [8,10] [15,18]
[1,4] [4,5]                  // → [1,5]
[1,4] [5,6]                  // → [1,4] [5,6]

Walkthrough

Thinking it through

In arbitrary order, deciding which intervals overlap means comparing every interval against every other — O(n²), since an interval near the end could overlap one near the start with no structure to shortcut the search.

Why sorting removes the hard part

Overlap is about positions on a line. Once sorted by start, anything that could overlap the current interval must be adjacent to it in that order — nothing else in the list is a candidate. If B doesn't overlap A (A's start comes first), nothing starting even later than B can overlap A either. Sorting turns a global "could overlap anything" problem into a local "compare to the immediately previous one" problem.

Building the sweep

Sort intervals by start.
Initialize the current merged interval to the first one.
For each next interval: if its start falls within (or at) the current's end, they overlap — extend the current's end to the larger of the two (never just replace, since the new interval might end earlier).
If the next interval starts strictly after the current's end, there's a gap — emit the current as finished, and the next interval becomes the new current.
Emit whatever's left as the final current.

Why this is correct and efficient

Since intervals are processed in increasing start order, once you've moved past one, nothing later can retroactively affect it — later intervals can only extend the current merged interval forward, never reopen a finished one. A single left-to-right sweep suffices.

Cost is dominated by the sort, O(n log n); the sweep itself is O(n). When a problem is about overlapping or ordered ranges, sorting by one coordinate often converts an all-pairs comparison into a linear sweep.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.