Interval Problems: Core Insight
Interval problems involve ranges [start, end]. The key operations: merge overlapping intervals, find non-overlapping sets, detect conflicts, and count active intervals at a point in time. The universal first step: sort by start time. After sorting, overlapping intervals are always adjacent.
Pattern 1: Merge Overlapping Intervals
def merge(intervals: list) -> list:
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlap: start <= prev_end
merged[-1][1] = max(merged[-1][1], end) # extend
else:
merged.append([start, end]) # no overlap: add new
return merged
# Time O(n log n) for sort, O(n) for merge. Space O(n).
Pattern 2: Insert Interval
def insert(intervals: list, new: list) -> list:
result = []
i = 0
# Add all intervals that end before new starts
while i < len(intervals) and intervals[i][1] < new[0]:
result.append(intervals[i]); i += 1
# Merge all overlapping intervals with new
while i < len(intervals) 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 < len(intervals):
result.append(intervals[i]); i += 1
return result
# Time O(n), Space O(n). No sort needed (input is already sorted).
Pattern 3: Meeting Rooms (Can Attend All?)
def canAttendMeetings(intervals: list) -> bool:
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]: # next starts before prev ends
return False
return True
Pattern 4: Meeting Rooms II (Minimum Rooms)
How many rooms are needed to schedule all meetings? Use a min-heap of end times. The heap represents rooms in use. For each meeting (sorted by start): if the earliest-ending room finishes before this meeting starts, reuse it (pop and push new end). Otherwise, open a new room (push new end). Heap size = rooms needed.
import heapq
def minMeetingRooms(intervals: list) -> int:
intervals.sort(key=lambda x: x[0])
heap = [] # min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse room
else:
heapq.heappush(heap, end) # new room
return len(heap)
# Equivalent: "sweep line" — events at start (+1) and end (-1), track max active
Pattern 5: Non-Overlapping Intervals (Minimum Removals)
Find the minimum number of intervals to remove to make the rest non-overlapping. Greedy: sort by end time. Always keep the interval that ends earliest (leaves the most room for future intervals). When there is a conflict, remove the one with the later end time.
def eraseOverlapIntervals(intervals: list) -> int:
intervals.sort(key=lambda x: x[1]) # sort by END time (greedy)
removed = 0
prev_end = float('-inf')
for start, end in intervals:
if start >= prev_end:
prev_end = end # keep this interval
else:
removed += 1 # remove current (later end) — keep prev
return removed
Pattern 6: Interval List Intersections
def intervalIntersection(A: list, B: list) -> list:
i = j = 0
result = []
while i < len(A) and j < len(B):
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
result.append([lo, hi])
# Advance the interval that ends first
if A[i][1] < B[j][1]: i += 1
else: j += 1
return result
# Time O(m + n), Space O(m + n).
Pattern 7: Employee Free Time
Given schedules for N employees (lists of intervals), find common free time. Merge all intervals, then find gaps between consecutive merged intervals.
def employeeFreeTime(schedules: list) -> list:
all_intervals = sorted([iv for schedule in schedules for iv in schedule])
merged = [all_intervals[0][:]]
for start, end in all_intervals[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
# Gaps between consecutive merged intervals = free time
return [[merged[i][1], merged[i+1][0]] for i in range(len(merged)-1)]
Sweep Line Pattern
For counting “how many intervals are active at time T” or “maximum overlap count”:
def maxOverlap(intervals: list) -> int:
events = []
for start, end in intervals:
events.append((start, 1)) # +1 at start
events.append((end, -1)) # -1 at end
events.sort()
active = max_active = 0
for time, delta in events:
active += delta
max_active = max(max_active, active)
return max_active
Decision Guide
- Merge intervals → sort by start, sweep and extend.
- Minimum rooms / maximum overlap → min-heap of end times or sweep line.
- Minimum removals → sort by end time (greedy keeps earliest-ending).
- Two-list intersection → two-pointer, advance whichever ends first.
- Free time / gaps → merge all, then iterate adjacent pairs.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide