Interval Problem Fundamentals
Interval problems involve ranges [start, end] and ask about overlaps, merges, insertions, or optimal scheduling. The key operation is determining whether two intervals overlap: [a, b] and [c, d] overlap if and only if a < d AND c < b (strict) — equivalently, max(a, c) < min(b, d). Most interval problems require sorting by start time as the first step.
Merge Intervals (LC 56)
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last = merged[-1]
if start current end.
# If start <= current end, they overlap (or touch) and we extend.
Insert Interval (LC 57)
def insert(intervals: list[list[int]],
new_interval: list[int]) -> list[list[int]]:
result = []
i = 0
n = len(intervals)
# 1. Add all intervals that end before new_interval starts
while i < n and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
# 2. Merge all intervals that overlap with new_interval
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)
# 3. Add all remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
Meeting Rooms II — Minimum Conference Rooms (LC 253)
import heapq
def min_meeting_rooms(intervals: list[list[int]]) -> int:
"""Minimum rooms needed so all meetings can run simultaneously."""
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
# Min-heap of end times (tracks when each room becomes free)
heap = []
for start, end in intervals:
if heap and heap[0] int:
starts = sorted(s for s, e in intervals)
ends = sorted(e for s, e in intervals)
rooms = rooms_needed = 0
j = 0
for s in starts:
rooms += 1
rooms_needed = max(rooms_needed, rooms)
if s >= ends[j]:
rooms -= 1
j += 1
return rooms_needed
Non-Overlapping Intervals (LC 435)
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
"""Minimum number of intervals to remove to make the rest non-overlapping."""
intervals.sort(key=lambda x: x[1]) # Sort by END time (activity selection)
count = 0
prev_end = float('-inf')
for start, end in intervals:
if start >= prev_end:
prev_end = end # Keep this interval
else:
count += 1 # Remove this interval (it overlaps with previous kept)
return count
# Greedy: always keep the interval with the earliest end time.
# Proof: keeping the interval with the smallest end leaves maximum room
# for future intervals. Any interval with a later end time would block
# at least as many future intervals as the one with the earliest end.
Employee Free Time (LC 759)
def employee_free_time(schedule: list[list[list[int]]]) -> list[list[int]]:
"""
Find common free time across all employees.
schedule[i] = sorted list of [start, end] intervals for employee i.
"""
# Flatten all intervals, sort by start time
all_intervals = sorted(
[interval for employee in schedule for interval in employee],
key=lambda x: x[0]
)
# Merge all intervals to find "busy time"
merged = [all_intervals[0][:]]
for s, e in all_intervals[1:]:
if s <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], e)
else:
merged.append([s, e])
# Gaps between merged intervals = common free time
free = []
for i in range(1, len(merged)):
free.append([merged[i-1][1], merged[i][0]])
return free
Interval List Intersections (LC 986)
def interval_intersection(A: list[list[int]],
B: list[list[int]]) -> list[list[int]]:
"""Find all intersections between sorted interval lists A and 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 pointer for whichever interval ends sooner
if A[i][1] = its end.
Pattern Recognition Guide
- Merge overlapping intervals → sort by start, merge greedily
- Maximum concurrent events / minimum rooms → sort by start, min-heap of end times (or two-pointer on sorted starts/ends)
- Maximum non-overlapping intervals (activity selection) → sort by END time, greedy keep
- Insert into sorted interval list → three-phase: skip non-overlapping left, merge overlapping, append remaining
- Intersection of two sorted interval lists → two-pointer, advance smaller end
- Free time across multiple schedules → flatten + merge, find gaps
The sorting key matters: sort by start for merge/insert; sort by end for activity selection (greedy). When minimum rooms/maximum events at one time: think of it as a sweep line — +1 when a meeting starts, -1 when it ends. The maximum running sum = answer.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide