Merge Intervals

Given a list of intervals, merge all overlapping intervals and return the result.

Function signature

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

Inputs / outputs

• intervals: each element is [start, end] with start <= end.
• Return: merged, non-overlapping intervals sorted by start.

Example

intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Constraints

• 0 <= len(intervals) <= 100_000
• -1_000_000_000 <= start <= end <= 1_000_000_000

Core idea (near-solution)

Sort by start. Then scan and merge into a running interval.

Invariant: the output list is always non-overlapping and sorted.

Algorithm (step-by-step)

1. Sort intervals by start (and end as tie-breaker).
2. Initialize current = first interval.
3. For each next interval:
   • If it overlaps (next.start <= current.end), extend current.end.
   • Else, append current and start a new current.
4. Append the final current.

Correctness sketch

• Invariant: the output list is always non-overlapping and sorted.
• Sorting establishes a consistent processing order.
• Merge/greedy steps maintain a correct partial solution.
• After processing all intervals, the result is optimal and complete.

Trace (hand walkthrough)

Example input:
intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]

Walk:
- start [1,3]; merge [2,6] -> [1,6]
- next [8,10] no overlap -> keep
- next [15,18] no overlap -> keep -> [[1,6],[8,10],[15,18]]

Pitfalls to avoid

• Not sorting before merging.
• Using strict < instead of <= for overlap detection.

Complexity

• Time: O(n log n) due to sorting.
• Extra space: O(n) for the output.

Implementation notes (Go)

• Sort by start ascending.
• Append the last merged interval after the loop.