Interval Patterns
Sort by an endpoint, then sweep. Merging, inserting, and counting overlaps — the shape most scheduling problems take.
Intervals turn scheduling, calendars, reservations, and ranges into the same shape: each item has a start and an end, and the question is how those spans interact. The hard part is rarely the data structure. It is choosing the right sort order and being precise about overlap.
Most interval solutions start by sorting, then sweeping left to right. Sort by start when you need to merge or insert. Sort by end when you need to choose as many compatible intervals as possible. Use a min-heap of end times when multiple active intervals can overlap at once.
The mental model
For closed intervals like [start, end], two intervals overlap when the next start is at or before the current end:
def overlaps(a, b):
return a[0] <= b[1] and b[0] <= a[1]After sorting by start, merging is just keeping one current interval and either extending it or flushing it:
def merge_sorted(intervals):
merged = []
for start, end in intervals:
if not merged or start > merged[-1][1]:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
return mergedFor room-counting problems, think of a sweep line. Starts add one active meeting; ends remove one. A min-heap stores the earliest ending active meeting, so before placing a new meeting you remove every meeting that already ended.
Meeting rooms usually use half-open time ranges: a meeting ending at 10 does not conflict with one starting at 10. That changes the condition from overlap to reuse: if earliest_end <= start, the room is free.
Pattern recognition
Variations
Worked problems
Try each yourself before revealing the solution. Watch how the same sorted sweep changes slightly with the question.
Merge Intervals
Given a list of intervals, combine all overlapping intervals and return a list of non-overlapping ranges that cover the same values.
Approach. Sort by start. The last interval in merged is the only interval that can overlap the next one, because everything before it ends no later. If the next start is beyond the last end, start a new interval. Otherwise extend the last end if needed.
Show solution
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for start, end in intervals:
if not merged or start > merged[-1][1]:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
return mergedComplexity. O(n log n) time from sorting and O(n) space for the output. The sweep after sorting is linear.
Insert Interval
You are given sorted, non-overlapping intervals and one new interval. Insert the new interval into the correct position and merge if it overlaps neighbors.
Approach. Because the existing intervals are already sorted, no full sort is needed. Copy every interval that ends before the new interval starts. Then merge all intervals whose start is at or before the new interval’s end. Finally append the merged interval and the untouched suffix.
Show solution
def insert(intervals, new_interval):
result = []
i = 0
n = len(intervals)
new_start, new_end = new_interval
while i < n and intervals[i][1] < new_start:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= new_end:
new_start = min(new_start, intervals[i][0])
new_end = max(new_end, intervals[i][1])
i += 1
result.append([new_start, new_end])
result.extend(intervals[i:])
return resultComplexity. O(n) time and O(n) space. Each interval is copied or merged once, and the input’s sorted order is preserved.
Meeting Rooms II
Given meeting time ranges, return the minimum number of rooms required so every meeting can be scheduled. A meeting that starts exactly when another ends can use the same room.
Approach. Sort meetings by start time. Keep a min-heap of end times for currently active meetings. Before adding the next meeting, pop every meeting that ended at or before its start. After pushing the new end time, the heap size is the number of rooms active at that moment.
Show solution
import heapq
def min_meeting_rooms(intervals):
intervals.sort(key=lambda x: x[0])
active_ends = []
rooms = 0
for start, end in intervals:
while active_ends and active_ends[0] <= start:
heapq.heappop(active_ends)
heapq.heappush(active_ends, end)
rooms = max(rooms, len(active_ends))
return roomsComplexity. O(n log n) time and O(n) space. Sorting dominates, and each meeting end is pushed and popped at most once.
The endpoint pitfall
If you are merging coverage, sort by start. If you are maximizing how many intervals survive, sort by end. If you are counting simultaneous activity, sweep with events or a min-heap. Most interval bugs come from using the right idea with the wrong endpoint rule.