6 drills · 6 pattern exercises · 11 micro drills
Patterns used in this topic, with difficulty breakdown.
Check if any meetings in your schedule overlap with each other.
All 6 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Given a list of time ranges that may overlap, combine any overlapping ranges into single ranges.
Sort by start time so overlapping intervals are adjacent. Then sweep left to right — if the current interval overlaps the last merged one, extend it; otherwise start a new merged interval.
Prompt
Given a collection of intervals, merge all overlapping intervals and return the non-overlapping intervals.
Solution
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlapping
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
# Test: merge([[1,3],[2,6],[8,10],[15,18]]) == [[1,6],[8,10],[15,18]]
# Test: merge([[1,4],[4,5]]) == [[1,5]]In plain English: Insert a new time range into an already-sorted list of non-overlapping ranges, merging any overlaps.
Three phases: (1) add all intervals that come entirely before the new one, (2) merge all overlapping intervals with the new one, (3) add all intervals that come entirely after. Clean linear scan.
Prompt
Given a sorted list of non-overlapping intervals and a new interval, insert the new interval and merge if necessary. Return the result sorted.
Solution
def insert(intervals, new):
result = []
i = 0
n = len(intervals)
# Phase 1: intervals entirely before new
while i < n and intervals[i][1] < new[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge overlapping intervals
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]),
max(new[1], intervals[i][1])]
i += 1
result.append(new)
# Phase 3: intervals entirely after
while i < n:
result.append(intervals[i])
i += 1
return result
# Test: insert([[1,3],[6,9]], [2,5]) == [[1,5],[6,9]]
# Test: insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])
# == [[1,2],[3,10],[12,16]]In plain English: Remove the fewest time ranges so that none of the remaining ones overlap.
Sort by end time (greedy activity selection). Always keep the interval that ends earliest — it leaves the most room for future intervals. Count how many you have to skip.
Prompt
Given an array of intervals, return the minimum number of intervals you need to remove to make the rest non-overlapping.
Solution
def erase_overlap_intervals(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end
removals = 0
prev_end = float('-inf')
for start, end in intervals:
if start < prev_end: # overlap
removals += 1 # remove this one (it ends later)
else:
prev_end = end # keep this one
return removals
# Test: erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]) == 1
# Test: erase_overlap_intervals([[1,2],[1,2],[1,2]]) == 2In plain English: Check if any meetings in your schedule overlap with each other.
Sort by start time, then check each consecutive pair. If any meeting starts before the previous one ends, there's a conflict. Sorting makes the check O(n).
Prompt
Given an array of meeting time intervals [[start, end], ...], determine if a person could attend all meetings (i.e., no two meetings overlap).
Solution
def can_attend_meetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]: # overlap
return False
return True
# Test: can_attend_meetings([[0,30],[5,10],[15,20]]) == False
# Test: can_attend_meetings([[7,10],[2,4]]) == TrueIn plain English: Figure out the fewest meeting rooms needed so every meeting has a room, even when meetings overlap.
Sort by start time. Use a min-heap tracking room end times. For each meeting, if it starts after the earliest-ending room, reuse that room (pop and push new end). Otherwise, allocate a new room. Heap size = rooms needed.
Prompt
Given an array of meeting time intervals, find the minimum number of conference rooms required.
Solution
import heapq
def min_meeting_rooms(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
rooms = [] # min-heap of end times
heapq.heappush(rooms, intervals[0][1])
for start, end in intervals[1:]:
if start >= rooms[0]: # can reuse earliest-ending room
heapq.heappop(rooms)
heapq.heappush(rooms, end)
return len(rooms)
# Test: min_meeting_rooms([[0,30],[5,10],[15,20]]) == 2
# Test: min_meeting_rooms([[7,10],[2,4]]) == 1In plain English: For each query value, find the smallest interval (by length) that contains it.
Sort intervals by start and queries by value. Sweep through queries in order, pushing applicable intervals onto a min-heap keyed by size. Pop expired intervals. The heap top is the smallest valid interval.
Prompt
Given a 2D array intervals and a queries array, for each query return the size of the smallest interval that contains the query. Return -1 if no interval contains it.
Solution
import heapq
def min_interval(intervals, queries):
intervals.sort()
result = {}
heap = [] # (size, end)
i = 0
for q in sorted(set(queries)):
# push all intervals that start <= q
while i < len(intervals) and intervals[i][0] <= q:
lo, hi = intervals[i]
heapq.heappush(heap, (hi - lo + 1, hi))
i += 1
# pop intervals that ended before q
while heap and heap[0][1] < q:
heapq.heappop(heap)
result[q] = heap[0][0] if heap else -1
return [result[q] for q in queries]
# Test: min_interval([[1,4],[2,4],[3,6],[4,4]], [2,3,4,5])
# == [3,3,1,4]6 exercises: spot the signals, pick the method, avoid the trap.
Given a collection of intervals, merge all overlapping intervals.
Signals
Sort by start. If current overlaps last merged, extend end. Else start new. O(n log n).
Same approach. Sort is the bottleneck at O(n log n); merge is O(n).
Trap
After sorting, compare with the LAST merged interval, not the previous input interval.
Given a sorted list of non-overlapping intervals and a new interval, insert and merge if necessary.
Signals
Add all before, merge overlapping ones, add all after. O(n).
Find insertion point with bisect, then merge. O(n) due to shifting.
Trap
Don't re-sort the entire list — it's already sorted. A single linear pass suffices.
Given intervals, find the minimum number of intervals to remove to make the rest non-overlapping.
Signals
Sort by end. Greedily keep intervals whose start >= last kept end. Removals = total - kept. O(n log n).
LIS-style on intervals sorted by end. O(n²) — less efficient.
Trap
Sort by END time, not start time. Sorting by start can lead to suboptimal greedy choices.
Given an array of meeting time intervals, determine if a person can attend all meetings.
Signals
Sort by start. If any interval starts before the previous ends, return False. O(n log n).
Merge intervals; if merged count < original count, there's overlap.
Trap
Don't check all pairs O(n²) — sorting first makes it a single linear scan.
Given meeting time intervals, find the minimum number of conference rooms required.
Signals
Sort by start. Min-heap of end times. If earliest end <= current start, reuse room. Else add room. O(n log n).
Separate starts and ends into sorted arrays. Sweep with two pointers counting active meetings. O(n log n).
Trap
Don't try to simulate rooms directly. The heap tracks the earliest-ending meeting for reuse.
Given intervals and queries (points), for each query find the size of the smallest interval containing it.
Signals
Sort queries and intervals. For each query, push valid intervals to min-heap. Pop expired. O((n+q) log n).
For each query, binary search for valid intervals. Less efficient without sorting.
Trap
Process queries offline (sorted) to avoid redundant work. Don't scan all intervals per query.
11 quick recall drills to reinforce this topic.
Sort-then-merge is the standard O(n log n) approach to interval union.
a.sort()
res = [a[0]]
for s, e in a[1:]:
if s <= res[-1][1]:
res[-1][1] = max(res[-1][1], e)
else:
res.append([s, e])Custom key sorting is Python's primary sort mechanism. Foundation for interval and custom-order problems.
a.sort(key=lambda x: x[1])Multi-key sorting handles tiebreakers. Used in leaderboard and event scheduling.
a.sort(key=lambda x: (x[0], -x[1]))Greedy two-pointer moves the shorter wall inward. O(n) time, O(1) space.
l, r = 0, len(h)-1
mx = 0
while l < r:
mx = max(mx, min(h[l], h[r]) * (r - l))
if h[l] < h[r]: l += 1
else: r -= 1Two-pointer with running left/right max computes trapped water in O(n).
l, r = 0, len(h)-1
lm = rm = res = 0
while l < r:
if h[l] < h[r]:
lm = max(lm, h[l])
res += lm - h[l]
l += 1
else:
rm = max(rm, h[r])
res += rm - h[r]
r -= 1Greedy narrowing of left/right pointers maximizes area. Proof relies on the shorter-wall argument.
l, r = 0, len(h) - 1
best = 0
while l < r:
area = min(h[l], h[r]) * (r - l)
best = max(best, area)
if h[l] < h[r]: l += 1
else: r -= 1Sort by start, then check if each interval starts before the previous one ends. Foundation for meeting rooms.
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
return True # overlap
return FalseMove-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Heap tracks room end times. If the earliest-ending room is free, reuse it; otherwise allocate a new one.
import heapq
intervals.sort()
rooms = [] # min-heap of end times
for start, end in intervals:
if rooms and rooms[0] <= start:
heapq.heappop(rooms) # reuse room
heapq.heappush(rooms, end)
return len(rooms)heappop extracts the minimum. Pair with heappush for priority queue operations.
import heapq
heapq.heappop(h)Sortedness check is a precondition guard for binary search and merge operations.
all(a[i] <= a[i+1] for i in range(len(a)-1))