4 questions using this pattern
Process and manipulate intervals (ranges) that may share common regions. The key insight is that sorting intervals by start time allows efficient detection and handling of overlaps through a single linear pass.
Imagine scheduling meeting rooms. Each meeting is an interval of time. When two meetings overlap, you need either two rooms or to merge them into one longer booking. By sorting meetings by start time, you can easily spot overlaps—if the next meeting starts before the current one ends, they overlap.
Another analogy: merging overlapping highlighter marks on a page. Sort them left to right, and if one mark starts before the previous ends, combine them into one continuous highlight.
The interval pattern relies on sorting intervals by start time. Once sorted, overlapping detection becomes simple:
Two intervals [a, b] and [c, d] overlap if c <= b (assuming a <= c after sorting)
Key operations:
For problems needing simultaneous tracking (like minimum meeting rooms), use a sweep line approach: sort all start and end points together, then sweep through counting active intervals.
def merge(intervals: list[list[int]]) -> list[list[int]]: if len(intervals) <= 1: return intervals # Sort by start time intervals.sort(key=lambda x: x[0]) merged = [intervals[0]] for current in intervals[1:]: last = merged[-1] if current[0] <= last[1]: # Overlap last[1] = max(last[1], current[1]) else: merged.append(current) return mergedGiven intervals [[1,3], [2,6], [8,10], [15,18]], merge all overlapping intervals. Notice [1,3] and [2,6] share the range [2,3].
Merging overlapping intervals:
Input: [[1,3], [2,6], [8,10], [15,18]]
(sorted by start)
Process [1,3]: result = [[1,3]]
Process [2,6]: 2 <= 3? Yes, overlap!
Merge: [1, max(3,6)] = [1,6]
result = [[1,6]]
Process [8,10]: 8 <= 6? No, no overlap
result = [[1,6], [8,10]]
Process [15,18]: 15 <= 10? No, no overlap
result = [[1,6], [8,10], [15,18]]
Visualized on number line:
Before: [1---3]
[2------6]
[8--10]
[15--18]
After: [1--------6] [8--10] [15--18]
Meeting rooms (sweep line):
Meetings: [[0,30], [5,10], [15,20]]
Events (sorted):
time=0: +1 (start) active=1
time=5: +1 (start) active=2 ← max
time=10: -1 (end) active=1
time=15: +1 (start) active=2 ← max
time=20: -1 (end) active=1
time=30: -1 (end) active=0
Max concurrent = 2 → need 2 meeting rooms
Use this skeleton as a starting point for problems using this pattern:
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
"""Merge overlapping intervals."""
if not intervals:
return []
# Sort by start time
intervals.sort(key=lambda x: x[0])
result = [intervals[0]]
for start, end in intervals[1:]:
last_end = result[-1][1]
if start <= last_end: # Overlap
result[-1][1] = max(last_end, end) # Extend
else:
result.append([start, end])
return result
def insert_interval(intervals: list[list[int]],
new: list[int]) -> list[list[int]]:
"""Insert and merge a new interval into sorted list."""
result = []
i = 0
n = len(intervals)
# Add all intervals before new interval
while i < n and intervals[i][1] < new[0]:
result.append(intervals[i])
i += 1
# Merge overlapping intervals with new
while i < n and intervals[i][0] <= new[1]:
new[0] = min(new[0], intervals[i][0])
new[1] = max(new[1], intervals[i][1])
i += 1
result.append(new)
# Add remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
def min_meeting_rooms(intervals: list[list[int]]) -> int:
"""Find minimum meeting rooms needed (sweep line)."""
events = []
for start, end in intervals:
events.append((start, 1)) # +1 for start
events.append((end, -1)) # -1 for end
# Sort by time, with ends before starts at same time
events.sort(key=lambda x: (x[0], x[1]))
max_rooms = 0
current_rooms = 0
for _, delta in events:
current_rooms += delta
max_rooms = max(max_rooms, current_rooms)
return max_rooms
def interval_intersection(A: list[list[int]],
B: list[list[int]]) -> list[list[int]]:
"""Find intersection of two sorted interval lists."""
result = []
i = j = 0
while i < len(A) and j < len(B):
# Find overlap
start = max(A[i][0], B[j][0])
end = min(A[i][1], B[j][1])
if start <= end:
result.append([start, end])
# Advance the interval that ends first
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
def can_attend_all(intervals: list[list[int]]) -> bool:
"""Check if a person can attend all meetings."""
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
return False # Overlap found
return TrueLook for these keywords and patterns in problem descriptions:
Trying to process unsorted intervals leads to incorrect results because overlaps aren't detected properly.
Fix:
Always sort intervals by start time before processing:
intervals.sort(key=lambda x: x[0])
Using start < last_end instead of start <= last_end misses adjacent
intervals that should be merged (like [1,2] and [2,3]).
Fix:
Use <= for touching intervals, < for strict overlap only. Check problem
requirements for whether touching counts as overlapping.
Combine all overlapping intervals into non-overlapping intervals.
Examples: Merge Intervals
Insert a new interval into a sorted list, merging with any overlapping intervals.
Examples: Insert Interval
Find minimum resources needed for concurrent intervals using sweep line or min-heap.
Examples: Meeting Rooms II, Car Pooling
Find common regions between two lists of intervals using two pointers.
Examples: Interval List Intersections
Find minimum removals to make all intervals non-overlapping. Greedy approach: keep intervals that end earliest.
Examples: Non-overlapping Intervals, Erase Overlap Intervals
Master the pattern with these representative problems.
Explore similar techniques:
Use two pointers to traverse data from different positions, often moving toward or away from each other. This technique transforms O(n²) brute force into O(n) by eliminating redundant comparisons.
Make locally optimal choices at each step, hoping to find a global optimum. Greedy algorithms are simple and efficient but only work when the problem has the greedy choice property—local optima lead to global optimum.
Setting end = new_end instead of end = max(old_end, new_end) fails when
a smaller interval is contained within a larger one.
Fix:
Always take the maximum:
result[-1][1] = max(result[-1][1], end)
Confusion about whether interval endpoints are inclusive [a, b] or
exclusive [a, b) causes incorrect overlap detection.
Fix:
Clarify the convention from the problem. Most problems use closed intervals where both endpoints are included.