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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the key insight for merging overlapping intervals?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Sort intervals by start time. Then scan linearly: if the current interval start is u2264 last merged end, merge by taking max(ends). Otherwise, push the current interval as a new entry. Time O(n log n) for sort + O(n) scan.”
}
},
{
“@type”: “Question”,
“name”: “How do you solve Meeting Rooms II (minimum conference rooms needed)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Sort meetings by start time. Maintain a min-heap of end times. For each meeting, if its start u2265 heap.top, pop (reuse that room). Always push the current end onto the heap. The heap size at the end equals the rooms needed. Time O(n log n), Space O(n).”
}
},
{
“@type”: “Question”,
“name”: “What is the difference between merge intervals and non-overlapping intervals?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Merge intervals combines overlapping segments and is solved by sorting by start. Non-overlapping intervals (Leetcode 435) asks how many to remove to make all non-overlapping u2014 sort by END time and use activity selection greedy: keep an interval if its start u2265 last kept end.”
}
},
{
“@type”: “Question”,
“name”: “How do you insert a new interval into a sorted non-overlapping list?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use a 3-phase approach: (1) add all intervals that end before the new interval starts, (2) merge all overlapping intervals into the new interval by expanding [min(starts), max(ends)], (3) add the remaining non-overlapping intervals. Time O(n).”
}
},
{
“@type”: “Question”,
“name”: “When should I sort intervals by start vs. by end?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Sort by START for: merging intervals, inserting intervals, finding overlaps. Sort by END for: activity selection (maximise non-overlapping count), finding free time windows, scheduling jobs to maximise count. The pattern: “keep as many as possible” u2192 sort by end.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide