Merge Overlapping Intervals in DSA Python

Mental Model

We combine intervals that touch or overlap into one bigger interval so there are no overlaps left.

Analogy: Imagine you have several time blocks booked on a calendar. If some blocks overlap or touch, you merge them into one longer block to avoid confusion.

Intervals before merge:
[1,3]  [2,6]  [8,10]  [15,18]

Intervals after merge:
[1,6]  [8,10]  [15,18]

Dry Run Walkthrough

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

Goal: Merge all overlapping intervals into combined intervals without overlaps

Step 1: Sort intervals by start time

[1,3] -> [2,6] -> [8,10] -> [15,18]

Why: Sorting helps us check intervals in order to find overlaps easily

Step 2: Start with first interval [1,3] in merged list

merged: [1,3]

Why: We need a base interval to compare others against

Step 3: Compare next interval [2,6] with last merged [1,3]; they overlap

merged: [1,6]

Why: Since 2 ≤ 3, intervals overlap; merge by extending end to max(3,6)=6

Step 4: Compare next interval [8,10] with last merged [1,6]; no overlap

merged: [1,6] -> [8,10]

Why: 8 > 6 means no overlap; add new interval to merged list

Step 5: Compare next interval [15,18] with last merged [8,10]; no overlap

merged: [1,6] -> [8,10] -> [15,18]

Why: 15 > 10 means no overlap; add new interval

Result:

merged intervals: [1,6] -> [8,10] -> [15,18]

Annotated Code

DSA Python

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # Sort intervals by start time
        intervals.sort(key=lambda x: x[0])
        merged = []
        for interval in intervals:
            # If merged is empty or no overlap, add interval
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # Overlap: merge by updating the end of last interval
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

# Driver code
intervals = [[1,3], [2,6], [8,10], [15,18]]
sol = Solution()
result = sol.merge(intervals)
for interval in result:
    print(f"[{interval[0]},{interval[1]}]", end=" ")

intervals.sort(key=lambda x: x[0])

Sort intervals by their start time to process in order

if not merged or merged[-1][1] < interval[0]:

Check if current interval does not overlap with last merged

merged.append(interval)

Add non-overlapping interval to merged list

merged[-1][1] = max(merged[-1][1], interval[1])

Merge overlapping intervals by extending the end time

Output

[1,6] [8,10] [15,18] 

Complexity Analysis

Time: O(n log n) because sorting the intervals takes O(n log n) and merging takes O(n)

Space: O(n) because in worst case no intervals overlap and merged list stores all intervals

vs Alternative: Naive approach checking every pair for overlap is O(n^2), so sorting + one pass merge is more efficient

Edge Cases

empty intervals list

returns empty list without error

DSA Python

if not merged or merged[-1][1] < interval[0]:

all intervals non-overlapping

returns original intervals sorted

DSA Python

if not merged or merged[-1][1] < interval[0]:

all intervals overlapping into one big interval

returns single merged interval covering all

DSA Python

merged[-1][1] = max(merged[-1][1], interval[1])

When to Use This Pattern

When you see a problem asking to combine or simplify overlapping ranges, reach for the merge intervals pattern because sorting and merging in one pass solves it efficiently.

Common Mistakes

Mistake: Not sorting intervals before merging
Fix: Always sort intervals by start time first to ensure correct merging order

Mistake: Modifying original intervals without copying
Fix: Be careful if input should not be changed; otherwise, modifying in place is fine

Summary

Merges overlapping intervals into combined intervals without overlaps.

Use when you need to simplify or combine overlapping ranges efficiently.

Sort intervals first, then merge by comparing current interval with last merged.