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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the key insight for solving interval merge problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “After sorting intervals by start time, overlapping intervals are always adjacent. Two intervals [a,b] and [c,d] overlap if and only if c = prev_end), keep it. Otherwise, remove it (it overlaps and has a later end time u2014 worse choice). This is the same greedy used in the Activity Selection Problem. Sorting by start time would not give the optimal greedy choice for this problem.”
}
},
{
“@type”: “Question”,
“name”: “How do you find the intersection of two sorted interval lists?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Two-pointer approach: maintain pointers i and j into lists A and B. The intersection of A[i] and B[j] is [max(A[i].start, B[j].start), min(A[i].end, B[j].end)] u2014 valid only if lo <= hi. After checking, advance the pointer whose interval ends first (it can no longer intersect with any remaining interval in the other list). This runs in O(m+n) time u2014 each interval is visited once. The two-pointer pattern works because both lists are sorted, so advancing the earlier-ending interval is always correct (it can't intersect future intervals in the other list either)."
}
},
{
"@type": "Question",
"name": "What is the sweep line technique and when do you use it for intervals?",
"acceptedAnswer": {
"@type": "Answer",
"text": "The sweep line converts interval problems into event-based problems. Create events: (start_time, +1) and (end_time, -1) for each interval. Sort all events by time (break ties by putting end events before start events if overlapping at a point should not count). Sweep through events, maintaining a running count of active intervals. The maximum count = maximum overlap at any point. Use sweep line for: maximum number of simultaneously active intervals, counting events at a time point, finding time ranges when N or more intervals overlap. It is equivalent to the min-heap approach for meeting rooms but easier to extend to general counting problems."
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide