Intervals

LeetCode 56

LeetCode #56Difficulty: MediumNeetCode 150

LeetCode 56: Merge Intervals

LeetCode

Given an array of intervals, merge all overlapping intervals.

Problem Description

Given an array of `intervals` where `intervals[i] = [start_i, end_i]`, merge all overlapping intervals, and return an array of the non-overlapping intervals.

Examples:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Constraints:
  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2

Core Mental Model

Sort intervals by start time. Iterate through: if the current interval starts before or at the previous end time, merge them: end = max(prev.end, curr.end).

Formal Loop Invariant

Invariant: Output list contains merged, non-overlapping intervals in ascending order.

Key Architectural Takeaway:

Sorting intervals by start time reduces overlap detection from O(N²) to O(N log N) linear scan.

Asymptotic Complexity Analysis

Time ComplexityO(N log N) for sortLinear scan
Space ComplexityO(N) for output.Constant auxiliary

Bottleneck: Dominated by initial sort.

Edge Cases & Screener Traps

  • Adjacent boundaries [1, 4] and [4, 5] overlap
  • Single interval