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)
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you merge overlapping intervals efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort by start time: O(n log n). Then scan left to right with one pass: O(n). Maintain a "current" interval. For each next interval: if next.start <= current.end, they overlap — extend current to max(current.end, next.end). Otherwise, finalize current and start a new one. The key insight: after sorting by start, two intervals overlap if and only if the second one starts before the first ends. Total: O(n log n) dominated by sort.”}},{“@type”:”Question”,”name”:”How do you find the minimum number of meeting rooms needed?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sweep line approach: create events list with (time, +1) for each start and (time, -1) for each end. Sort by time (ends before starts at the same time to free rooms before needing them). Scan events accumulating a running count — the maximum running count is the answer. Alternative: sort intervals by start time, use a min-heap of end times. For each new meeting, if it starts after the heap minimum (earliest free room), replace that entry — otherwise add a new room. Heap size at the end = rooms needed.”}},{“@type”:”Question”,”name”:”What is the greedy approach for minimum interval removal?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Sort intervals by END time (not start time — this is the critical insight). Greedily keep the interval with the earliest end: it leaves the most room for future intervals. When two intervals overlap, remove the one with the later end time (the current one, since we’ve already kept the earlier-ending one). This is the activity selection problem — the classic greedy algorithm for maximum non-overlapping intervals. To get minimum removals: total_intervals – max_non_overlapping.”}},{“@type”:”Question”,”name”:”How do you insert a new interval into a sorted non-overlapping list?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Three phases in one pass: (1) Copy all intervals that end strictly before the new interval starts (no overlap). (2) Merge all intervals that overlap with the new interval by expanding its boundaries: new.start = min(new.start, current.start), new.end = max(new.end, current.end). (3) Append the merged new interval, then copy all remaining intervals. Total: O(n) time, no additional sorting needed because the input is already sorted.”}},{“@type”:”Question”,”name”:”How do you find intersections between two sorted interval lists?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Use two pointers, one per list. At each step: compute intersection of A[i] and B[j] as [max(A[i].start, B[j].start), min(A[i].end, B[j].end)]. If lo <= hi, it’s a valid intersection — add to result. Then advance the pointer for the interval that ends first (it can’t intersect with any more intervals from the other list). This is O(m + n) — optimal since you may need to output up to O(m + n) intersections.”}}]}
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.