Merge Intervals

LeetCode 56 • Medium • Intervals

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

TimeO(n log n)sort + linear scan

SpaceO(n)result list

Index: — Current: — Result: —

Input

Current

Merged

Result

Current

—

Result

—

Speed:

Ready

Press Play. Sort by start, then scan: if next start ≤ current end, merge; else add new interval.

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.

# ─── MERGE INTERVALS (LeetCode 56) ───

# Pattern: Sort by start, merge when next_start ≤ curr_end

# Time: O(n log n) Space: O(1) output

# 1. Define: merge(intervals)

# 2. Base: if len(intervals) <= 1: return intervals

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

# 4. Build result: result = [intervals[0]]

# for i in range(1, len(intervals)):

# 5. Overlap? curr_end = result[-1][1]

# if intervals[i][0] <= curr_end: → merge: result[-1][1] = max(curr_end, intervals[i][1])

# else: result.append(intervals[i])

# 6. Return: return result

# Vars: result, curr_end, i

▼ your implementation ▼

Verify your solution: