Sorting & SearchingIntermediate
Merge Intervals
Sort intervals by start time, then merge overlapping ones by comparing end times.
Problem: Merge Overlapping Intervals
Merge overlapping intervals: [[1,3], [2,6], [8,10], [15,18]]
[1,3]
[2,6]
[8,10]
[15,18]
0
2
4
6
8
10
12
14
16
18
20
Not processedCurrentOverlapMerged
Show input intervals (already sorted by start)
Input: [[1,3], [2,6], [8,10], [15,18]]. These are already sorted by start time. We will process them left to right and merge overlapping intervals.
Current Interval--
Last Merged--
Overlap Check--
Merged Result[]
Step 1/6
Speed:
When to Use
- Overlapping intervals
- Meeting room scheduling
- Insert interval into sorted list
Key Indicators
- Intervals or ranges
- Overlapping/merging
- Scheduling problems
- Start/end times
Complexity
Time
O(n log n)
Space
O(n)
Common Problems
Merge IntervalsInsert IntervalMeeting RoomsNon-overlapping Intervals
Code
sort intervals by start time
merged = [intervals[0]]
for interval in intervals[1:]:
if interval.start <= merged[-1].end:
merged[-1].end = max(merged[-1].end, interval.end)
else:
merged.append(interval)Want all 29 patterns with detailed visual walkthroughs?
The complete book includes 84 practice problems, full decision tree, and illustrated step-by-step solutions.
Book Coming Soon ($4.99)