LeetCode 56: Merge Intervals Solution in Python Explained

Problem Statement

LeetCode 56, Merge Intervals, is a medium-level problem where you’re given an array of intervals intervals, where each interval is represented as [start, end] (inclusive). Your task is to merge all overlapping intervals and return an array of non-overlapping intervals that cover all the intervals in the input. The result can be in any order.

Constraints

  • 1 <= intervals.length <= 10^4: Number of intervals is between 1 and 10,000.
  • intervals[i].length == 2: Each interval has a start and end.
  • 0 <= start_i <= end_i <= 10^4: Start and end values are within this range.

Example

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap, merge into [1,6]; others are separate.

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] touch at 4, merge into [1,5].

Input: intervals = [[1,4],[2,3]]
Output: [[1,4]]
Explanation: [2,3] is fully contained within [1,4], merge into [1,4].

Understanding the Problem

How do you solve LeetCode 56: Merge Intervals in Python? For intervals = [[1,3],[2,6],[8,10],[15,18]], merge overlapping intervals to get [[1,6],[8,10],[15,18]]. Overlaps occur when one interval’s start is less than or equal to another’s end, requiring us to combine them. We’ll explore two approaches: a Sorting with Linear Scan Solution (optimal and primary) and an Alternative with Sweep Line (more complex but insightful). The sorting method runs in O(n log n) time by ordering intervals and merging in a single pass.

Solution 1: Sorting with Linear Scan Approach (Primary)

Explanation

Sort intervals by start time, then scan linearly to merge overlaps. Compare each interval with the last merged interval: if they overlap (current start ≤ last end), update the end to the maximum of the two ends; otherwise, add the current interval as a new segment.

Here’s a flow for [[1,3],[2,6],[8,10],[15,18]]:

Sort: [[1,3],[2,6],[8,10],[15,18]]
Scan: [1,3] -> [1,6] (merge [2,6]) -> [1,6],[8,10] -> [1,6],[8,10],[15,18]
  1. Sort Intervals.
  • Sort by start time, breaking ties by end time.
  1. Initialize Result.
  • Start with the first interval.
  1. Linear Scan.
  • Merge or append based on overlap.
  1. Return Merged Intervals.

Step-by-Step Example

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

We need [[1,6],[8,10],[15,18]].

  • Goal: Merge overlapping intervals.
  • Result for Reference: [[1,6],[8,10],[15,18]].
  • Start: intervals = [[1,3],[2,6],[8,10],[15,18]], sort = same (already sorted), result = [].
  • Step 1: Add [1,3].
    • result = [[1,3]].
  • Step 2: Check [2,6].
    • 2 ≤ 3 (overlap), update end = max(3, 6) = 6, result = [[1,6]].
  • Step 3: Check [8,10].
    • 8 > 6 (no overlap), append [8,10], result = [[1,6],[8,10]].
  • Step 4: Check [15,18].
    • 15 > 10 (no overlap), append [15,18], result = [[1,6],[8,10],[15,18]].
  • Finish: Return [[1,6],[8,10],[15,18]].

Example 2: intervals = [[1,4],[4,5]]

We need [[1,5]].

  • Start: Sort = [[1,4],[4,5]], result = [].
  • Step 1: Add [1,4].
    • result = [[1,4]].
  • Step 2: Check [4,5].
    • 4 ≤ 4 (overlap), update end = max(4, 5) = 5, result = [[1,5]].
  • Finish: Return [[1,5]].

How the Code Works (Sorting with Linear Scan)

Here’s the Python code with line-by-line explanation:

def merge(intervals: list[list[int]]) -> list[list[int]]:
    # Line 1: Handle edge case
    if not intervals:
        return []

    # Line 2: Sort intervals by start time
    intervals.sort(key=lambda x: x[0])

    # Line 3: Initialize result with first interval
    result = [intervals[0]]

    # Line 4: Linear scan to merge
    for i in range(1, len(intervals)):
        curr_start, curr_end = intervals[i]
        last_start, last_end = result[-1]
        # Line 5: Check for overlap
        if curr_start <= last_end:
            # Line 6: Merge by updating end
            result[-1][1] = max(last_end, curr_end)
        else:
            # Line 7: No overlap, append new interval
            result.append([curr_start, curr_end])

    # Line 8: Return merged intervals
    return result

Alternative: Sweep Line Approach

Explanation

Use a sweep line technique: treat each interval’s start and end as events, sort them, and sweep through to count overlaps. When the overlap count drops to 0, a merged interval ends; when it increases from 0, a new one starts.

  1. Create Events.
  • Start (+1), end (-1) for each interval.
  1. Sort Events.
  • By time, breaking ties with end events first.
  1. Sweep Line.
  • Track count, build merged intervals.
  1. Return Result.

Step-by-Step Example (Alternative)

For [[1,3],[2,6],[8,10],[15,18]]:

  • Start: Events = [(1,+1),(3,-1),(2,+1),(6,-1),(8,+1),(10,-1),(15,+1),(18,-1)].
  • Step 1: Sort = [(1,+1),(2,+1),(3,-1),(6,-1),(8,+1),(10,-1),(15,+1),(18,-1)].
  • Step 2: Sweep.
    • t=1, count=1, start=1.
    • t=2, count=2.
    • t=3, count=1.
    • t=6, count=0, end=6, result=[[1,6]].
    • t=8, count=1, start=8.
    • t=10, count=0, end=10, result=[[1,6],[8,10]].
    • t=15, count=1, start=15.
    • t=18, count=0, end=18, result=[[1,6],[8,10],[15,18]].
  • Finish: Return [[1,6],[8,10],[15,18]].

How the Code Works (Sweep Line)

def mergeSweep(intervals: list[list[int]]) -> list[list[int]]:
    # Line 1: Create events
    events = []
    for start, end in intervals:
        events.append((start, 1))  # Start event
        events.append((end, -1))   # End event

    # Line 2: Sort events (end events before start if tied)
    events.sort(key=lambda x: (x[0], -x[1]))

    # Line 3: Sweep line
    result = []
    count = 0
    start = None
    for time, delta in events:
        # Line 4: Update count
        count += delta
        # Line 5: Start new interval
        if count > 0 and start is None:
            start = time
        # Line 6: End interval
        elif count == 0 and start is not None:
            result.append([start, time])
            start = None

    # Line 7: Return merged intervals
    return result

Complexity

  • Sorting with Linear Scan:
    • Time: O(n log n) – Sorting dominates.
    • Space: O(1) – Only result list (excluding output).
  • Sweep Line:
    • Time: O(n log n) – Sorting events.
    • Space: O(n) – Store events.

Efficiency Notes

Sorting with Linear Scan is O(n log n) time and O(1) space (excluding output), optimal for LeetCode 56. Sweep Line is also O(n log n) time but uses O(n) space for events, less space-efficient but conceptually rich.

Key Insights

Tips to master LeetCode 56:

  • Sort First: Order by start time simplifies merging.
  • Overlap Rule: Current start ≤ last end defines overlap.
  • Single Pass: Merge efficiently after sorting.

Additional Example

For intervals = [[1,5],[2,3],[4,6]]:

  • Goal: [[1,6]].
  • Sorting: [[1,5],[2,3],[4,6]] -> [[1,6]] (merge all).
  • Result: [[1,6]].

Edge Cases

  • Single Interval: [[1,2]] – Return [[1,2]].
  • No Overlap: [[1,2],[3,4]] – Return [[1,2],[3,4]].
  • Empty: [] – Return [].

Final Thoughts

The Sorting with Linear Scan solution is a star for LeetCode 56 in Python—straightforward, efficient, and elegant. For a related challenge, try LeetCode 55: Jump Game to switch to array jumping! Ready to merge? Solve LeetCode 56 on LeetCode now and test it with [[1,3],[2,6]] or [[1,4],[2,3]] to master interval merging. Dive in and combine those ranges!