Why Interval Problems Matter in Interviews
Interval problems appear in scheduling, calendar, and range queries — and in coding interviews at every top company. The fundamental operations: merge overlapping intervals, insert a new interval into a sorted list, find the minimum number of rooms/resources to handle all intervals simultaneously, and determine if intervals conflict. Mastering these patterns unlocks a class of problems that look complex but reduce to simple sorted-order operations.
Pattern 1: Merge Overlapping Intervals
Sort by start time. Scan left to right; extend the current interval if the next overlaps, otherwise start a new one.
def merge_intervals(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps
merged[-1][1] = max(merged[-1][1], end) # extend
else:
merged.append([start, end]) # new interval
return merged
# Example: [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
# LeetCode 56 — O(n log n) sort + O(n) scan
Pattern 2: Insert Interval
Given a sorted non-overlapping list, insert a new interval and merge. Three phases: add all intervals that end before the new one starts, merge overlapping intervals, add all remaining intervals.
def insert_interval(intervals, new_interval):
result = []
i, n = 0, len(intervals)
# Phase 1: add all intervals ending before new_interval starts
while i < n and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge all overlapping intervals
while i < n and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
result.append(new_interval)
# Phase 3: add remaining intervals
result.extend(intervals[i:])
return result
# LeetCode 57 — O(n)
Pattern 3: Minimum Meeting Rooms (Sweep Line)
How many conference rooms do we need? Equivalent to: maximum number of overlapping intervals at any point. Use a sweep line: process starts (+1) and ends (-1) in sorted order.
def min_meeting_rooms(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # room needed
events.append((end, -1)) # room freed
events.sort(key=lambda x: (x[0], x[1])) # sort by time; ends before starts at same time
rooms = max_rooms = 0
for time, delta in events:
rooms += delta
max_rooms = max(max_rooms, rooms)
return max_rooms
# Alternative: min-heap to track earliest-ending meeting
import heapq
def min_meeting_rooms_heap(intervals):
intervals.sort()
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)
# LeetCode 253 — O(n log n)
Pattern 4: Non-Overlapping Intervals (Greedy)
Minimum number of intervals to remove to make the rest non-overlapping. Greedy: always keep the interval with the earliest end time (leaves more room for future intervals).
def erase_overlap_intervals(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[1]) # sort by END time
removed = 0
prev_end = intervals[0][1]
for start, end in intervals[1:]:
if start < prev_end: # overlap
removed += 1 # remove current (it ends later)
else:
prev_end = end # keep current, update boundary
return removed
# LeetCode 435 — O(n log n)
Pattern 5: Interval List Intersections
Given two sorted interval lists, find all intersecting intervals. Two-pointer approach:
def interval_intersection(A, B):
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
# LeetCode 986 — O(m + n)
Key Interview Tips
- Sort by start time for merge/insert problems; sort by end time for greedy scheduling problems
- Minimum rooms = maximum overlap at any point = sweep line with +1/-1 events
- Min-heap for room assignment: heap.top() = earliest room that becomes free
- Two pointers for sorted interval intersections — advance whichever interval ends first
- Greedy for removal problems: always keep the interval with the earliest end (maximizes future options)
Interval merge and scheduling algorithm patterns are tested in Google coding interview questions.
Interval and sweep line algorithm patterns are covered in Meta coding interview preparation.
Interval scheduling and meeting room problems appear in Amazon coding interview guide.