🎯 Interval Problems
1️⃣ Core Framework
When discussing Interval Problems, I frame it as:
- What interval problems are
- Interval overlap logic
- Sorting by start time
- Merging intervals
- Insert interval
- Meeting rooms
- Sweep line
- Min heap for active intervals
- Difference array
- Senior-level explanation
2️⃣ What Problem Are We Solving?
Interval problems involve ranges with a start and end.
They are commonly used for:
- Meeting schedule conflicts
- Calendar booking
- Merge intervals
- Insert interval
- Minimum meeting rooms
- Employee free time
- Airplane count
- Car pooling
- Range coverage
- Event overlap
- Sweep line problems
- CPU task scheduling windows
The core idea is:
An interval represents a continuous range.
Most interval problems are about overlap, merge, coverage, or ordering.
👉 Interview Answer
Interval problems are about ranges represented by a start and an end.
The key questions are usually: do two intervals overlap, can intervals be merged, how many intervals are active at the same time, or what gaps exist between intervals.
Most interval problems become easier after sorting by start time.
3️⃣ Basic Interval Representation
Common Format
Intervals are usually represented as:
[start, end]
Example:
intervals = [[1, 3], [2, 6], [8, 10]]
Meaning
An interval [1, 3] means:
starts at 1
ends at 3
Depending on the problem, the end can be inclusive or exclusive.
Important Detail
Meeting problems often treat intervals as:
[start, end)
This means:
a meeting ending at 10
does not conflict with a meeting starting at 10
👉 Interview Answer
Intervals are usually represented as start and end pairs.
One important detail is whether the end boundary is inclusive or exclusive.
In meeting room problems, intervals are usually treated as half-open ranges, so one meeting ending at time t does not overlap with another meeting starting at time t.
4️⃣ Overlap Logic
Two Intervals
Suppose we have:
a = [a_start, a_end]
b = [b_start, b_end]
They overlap if:
a_start <= b_end and b_start <= a_end
For inclusive intervals.
Non-Overlap Logic
Two intervals do not overlap if:
a_end < b_start
or
b_end < a_start
For meeting rooms with half-open ranges, non-overlap is usually:
a_end <= b_start
or
b_end <= a_start
Common Merge Condition
After sorting by start time, current interval overlaps previous interval if:
current_start <= previous_end
For inclusive merge problems.
👉 Interview Answer
Two intervals overlap when neither interval ends before the other starts.
After sorting intervals by start time, overlap checking becomes simple: if the current start is less than or equal to the previous end, the intervals overlap and can be merged.
5️⃣ Why Sorting Helps
Without Sorting
Intervals can appear in any order:
[8, 10], [1, 3], [2, 6]
It is hard to know which intervals should be compared.
With Sorting
Sort by start time:
[1, 3], [2, 6], [8, 10]
Now overlapping intervals become adjacent.
Key Insight
Most interval problems start with:
intervals.sort(key=lambda x: x[0])
Then scan from left to right.
👉 Interview Answer
Sorting by start time is usually the first step in interval problems.
Once intervals are sorted, overlapping intervals become adjacent.
This allows us to process intervals in one pass using the previous interval or a heap of active intervals.
6️⃣ Merge Intervals
Problem
Given intervals, merge all overlapping intervals.
Example:
[[1, 3], [2, 6], [8, 10], [15, 18]]
Output:
[[1, 6], [8, 10], [15, 18]]
Idea
Sort intervals by start.
Keep a result list.
For each interval:
if result is empty or no overlap:
append interval
else:
merge with last interval
Code
def merge(intervals):
intervals.sort(key=lambda x: x[0])
result = []
for start, end in intervals:
if not result or result[-1][1] < start:
result.append([start, end])
else:
result[-1][1] = max(result[-1][1], end)
return result
👉 Interview Answer
For merge intervals, I first sort intervals by start time.
Then I scan from left to right.
If the current interval does not overlap with the last merged interval, I append it.
Otherwise, I merge them by updating the end to the maximum end.
7️⃣ Insert Interval
Problem
Given a sorted list of non-overlapping intervals, insert a new interval and merge if needed.
Three Parts
When inserting a new interval:
1. intervals before new interval
2. intervals overlapping new interval
3. intervals after new interval
Code
def insert(intervals, new_interval):
result = []
i = 0
n = len(intervals)
new_start, new_end = new_interval
while i < n and intervals[i][1] < new_start:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= new_end:
new_start = min(new_start, intervals[i][0])
new_end = max(new_end, intervals[i][1])
i += 1
result.append([new_start, new_end])
while i < n:
result.append(intervals[i])
i += 1
return result
👉 Interview Answer
Insert Interval can be handled in three phases.
First, add all intervals that end before the new interval starts.
Second, merge all intervals that overlap with the new interval.
Third, add all remaining intervals after the merged interval.
This works because the input intervals are already sorted and non-overlapping.
8️⃣ Meeting Rooms
Problem
Given meeting time intervals, determine if a person can attend all meetings.
Key Idea
Sort by start time.
If any meeting starts before the previous meeting ends, there is a conflict.
Code
def can_attend_meetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
previous_end = intervals[i - 1][1]
current_start = intervals[i][0]
if current_start < previous_end:
return False
return True
Boundary Note
If one meeting ends at 10 and another starts at 10:
[1, 10]
[10, 12]
They do not conflict.
So condition is:
current_start < previous_end
not:
current_start <= previous_end
👉 Interview Answer
To check if someone can attend all meetings, I sort meetings by start time.
Then I compare each meeting with the previous one.
If the current meeting starts before the previous meeting ends, there is an overlap, so the person cannot attend all meetings.
9️⃣ Meeting Rooms II
Problem
Given meeting intervals, return the minimum number of rooms required.
Key Idea
We need to count how many meetings are active at the same time.
Use a min heap of end times.
Code
import heapq
def min_meeting_rooms(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
heap = []
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
return len(heap)
Why Heap?
The heap tracks the earliest ending active meeting.
If the earliest meeting ends before the current meeting starts, we can reuse that room.
👉 Interview Answer
Meeting Rooms II asks for the maximum number of overlapping meetings.
I sort meetings by start time and use a min heap to track active meeting end times.
If the earliest ending meeting ends before the current meeting starts, I reuse that room.
Otherwise, I need a new room.
The heap size represents the number of rooms currently needed.
🔟 Meeting Rooms II With Sweep Line
Alternative Approach
Separate starts and ends.
Sort both arrays.
Use two pointers.
Code
def min_meeting_rooms(intervals):
starts = sorted(interval[0] for interval in intervals)
ends = sorted(interval[1] for interval in intervals)
rooms = 0
max_rooms = 0
start_pointer = 0
end_pointer = 0
while start_pointer < len(intervals):
if starts[start_pointer] < ends[end_pointer]:
rooms += 1
max_rooms = max(max_rooms, rooms)
start_pointer += 1
else:
rooms -= 1
end_pointer += 1
return max_rooms
Boundary Detail
Use:
start < end
If start equals end, the previous meeting has ended and room can be reused.
👉 Interview Answer
Another way to solve Meeting Rooms II is sweep line.
I sort all start times and end times separately.
When the next start is before the next end, a new meeting begins and room count increases.
Otherwise, a meeting ends and room count decreases.
The maximum active count is the answer.
1️⃣1️⃣ Sweep Line Pattern
Core Idea
Sweep line converts intervals into events.
For each interval:
start event: +1
end event: -1
Then sort events by time and scan.
Example
Intervals:
[1, 3]
[2, 5]
[4, 6]
Events:
(1, +1)
(3, -1)
(2, +1)
(5, -1)
(4, +1)
(6, -1)
After sorting:
(1, +1)
(2, +1)
(3, -1)
(4, +1)
(5, -1)
(6, -1)
Code Skeleton
def sweep_line(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end, -1))
events.sort()
active = 0
max_active = 0
for time, delta in events:
active += delta
max_active = max(max_active, active)
return max_active
👉 Interview Answer
Sweep line turns intervals into start and end events.
A start event increases the active count. An end event decreases the active count.
After sorting events by time, scanning from left to right tells us how many intervals are active at each point.
1️⃣2️⃣ Sweep Line Tie-Breaking
Why Tie-Breaking Matters
When one interval ends at the same time another starts:
[1, 3]
[3, 5]
Do they overlap?
For meeting rooms:
No
Because the room can be reused.
Correct Event Order
For half-open intervals [start, end):
end event should be processed before start event
So at the same time:
-1 before +1
Code
def min_rooms_sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end, -1))
events.sort(key=lambda x: (x[0], x[1]))
active = 0
max_active = 0
for time, delta in events:
active += delta
max_active = max(max_active, active)
return max_active
Because -1 < 1,
end events are processed first.
👉 Interview Answer
Sweep line tie-breaking depends on interval semantics.
For meeting intervals, if one meeting ends at time t and another starts at time t, they do not overlap.
So end events should be processed before start events at the same timestamp.
1️⃣3️⃣ Employee Free Time
Problem
Given employees’ schedules, find common free time intervals.
Idea
Flatten all intervals, sort by start, merge busy intervals, then gaps between merged intervals are free time.
Code
def employee_free_time(schedule):
intervals = []
for employee in schedule:
for interval in employee:
intervals.append(interval)
intervals.sort(key=lambda x: x[0])
merged = []
for start, end in intervals:
if not merged or merged[-1][1] < start:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
free_time = []
for i in range(1, len(merged)):
previous_end = merged[i - 1][1]
current_start = merged[i][0]
if previous_end < current_start:
free_time.append([previous_end, current_start])
return free_time
👉 Interview Answer
For Employee Free Time, I flatten all employees’ busy intervals into one list.
Then I sort and merge busy intervals.
Any gap between consecutive merged busy intervals is common free time.
1️⃣4️⃣ Non-overlapping Intervals
Problem
Given intervals, return the minimum number of intervals to remove so the rest do not overlap.
Greedy Idea
Sort by end time.
Always keep the interval that ends earliest.
This leaves the most room for future intervals.
Code
def erase_overlap_intervals(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
removals = 0
previous_end = intervals[0][1]
for i in range(1, len(intervals)):
start, end = intervals[i]
if start < previous_end:
removals += 1
else:
previous_end = end
return removals
👉 Interview Answer
For Non-overlapping Intervals, I sort intervals by end time.
Greedily keeping the interval with the earliest end leaves the most room for later intervals.
If the next interval starts before the previous kept interval ends, it overlaps and should be removed.
Otherwise, I keep it and update the previous end.
1️⃣5️⃣ Minimum Number of Arrows to Burst Balloons
Problem
Each balloon is an interval.
One arrow at position x bursts all balloons where:
start <= x <= end
Return the minimum arrows needed.
Greedy Idea
Sort by end.
Shoot an arrow at the end of the first balloon.
If the next balloon starts after the arrow position, need a new arrow.
Code
def find_min_arrow_shots(points):
if not points:
return 0
points.sort(key=lambda x: x[1])
arrows = 1
arrow_position = points[0][1]
for start, end in points[1:]:
if start > arrow_position:
arrows += 1
arrow_position = end
return arrows
👉 Interview Answer
This is an interval greedy problem.
I sort balloons by end position.
Then I shoot an arrow at the earliest possible end.
If the next balloon starts after the current arrow position, the current arrow cannot burst it, so I need a new arrow.
1️⃣6️⃣ Interval List Intersections
Problem
Given two sorted interval lists, return their intersections.
Overlap Range
For two intervals:
[a_start, a_end]
[b_start, b_end]
Intersection is:
[max(a_start, b_start), min(a_end, b_end)]
Valid if:
start <= end
Code
def interval_intersection(first_list, second_list):
i = 0
j = 0
result = []
while i < len(first_list) and j < len(second_list):
start = max(first_list[i][0], second_list[j][0])
end = min(first_list[i][1], second_list[j][1])
if start <= end:
result.append([start, end])
if first_list[i][1] < second_list[j][1]:
i += 1
else:
j += 1
return result
👉 Interview Answer
For interval list intersections, both input lists are already sorted.
I use two pointers.
The intersection between two intervals is from the max start to the min end.
Then I move the pointer whose interval ends earlier, because that interval cannot intersect future intervals anymore.
1️⃣7️⃣ Remove Covered Intervals
Problem
Remove intervals that are fully covered by another interval.
Interval [a, b] covers [c, d] if:
a <= c and d <= b
Sorting Trick
Sort by:
start ascending
end descending
Why end descending?
For same start, the longer interval comes first and can cover shorter ones.
Code
def remove_covered_intervals(intervals):
intervals.sort(key=lambda x: (x[0], -x[1]))
count = 0
max_end = 0
for start, end in intervals:
if end > max_end:
count += 1
max_end = end
return count
👉 Interview Answer
For Remove Covered Intervals, I sort by start ascending and end descending.
Sorting end descending is important when two intervals have the same start, because the longer interval should come first.
Then I track the farthest end seen so far.
If the current end is not greater than that, the current interval is covered.
1️⃣8️⃣ Car Pooling
Problem
Each trip is:
[num_passengers, start, end]
Determine whether capacity is exceeded at any point.
Sweep Line
Passenger count changes at pickup and dropoff points.
start: +passengers
end: -passengers
Code
def car_pooling(trips, capacity):
events = []
for passengers, start, end in trips:
events.append((start, passengers))
events.append((end, -passengers))
events.sort()
current = 0
for location, delta in events:
current += delta
if current > capacity:
return False
return True
👉 Interview Answer
Car Pooling can be solved with sweep line.
Each pickup increases passenger count, and each dropoff decreases passenger count.
After sorting all events by location, I scan from left to right and check whether active passengers exceed capacity.
1️⃣9️⃣ Difference Array for Range Changes
When Coordinates Are Small
If the coordinate range is small, a difference array can be simpler than sorting events.
Idea
For interval update [start, end):
diff[start] += value
diff[end] -= value
Then prefix sum gives active count at each point.
Code
def car_pooling(trips, capacity):
diff = [0] * 1001
for passengers, start, end in trips:
diff[start] += passengers
diff[end] -= passengers
current = 0
for change in diff:
current += change
if current > capacity:
return False
return True
👉 Interview Answer
Difference array is useful when interval coordinates are small and bounded.
For each range, I add the change at the start and subtract it at the end.
Then a prefix scan gives the active value at every point.
This is essentially a discrete sweep line.
2️⃣0️⃣ Calendar Booking
Problem
Implement a calendar that books intervals if they do not overlap existing bookings.
Simple Approach
For each new booking, check it against all existing bookings.
Two intervals overlap if:
start < existing_end and existing_start < end
For half-open intervals.
Code
class MyCalendar:
def __init__(self):
self.bookings = []
def book(self, start, end):
for existing_start, existing_end in self.bookings:
if start < existing_end and existing_start < end:
return False
self.bookings.append([start, end])
return True
👉 Interview Answer
For My Calendar I, I store existing bookings.
For every new booking, I check whether it overlaps with any existing interval.
With half-open intervals, two bookings overlap if start is before existing end and existing start is before end.
If no overlap exists, I add the booking.
2️⃣1️⃣ My Calendar II
Problem
Allow double bookings, but reject triple bookings.
Idea
Track:
booked intervals
overlapped intervals
For every new interval:
if it overlaps any existing overlap interval:
triple booking exists
Otherwise, add new overlaps between new interval and booked intervals.
Code
class MyCalendarTwo:
def __init__(self):
self.bookings = []
self.overlaps = []
def book(self, start, end):
for overlap_start, overlap_end in self.overlaps:
if start < overlap_end and overlap_start < end:
return False
for booked_start, booked_end in self.bookings:
if start < booked_end and booked_start < end:
self.overlaps.append([
max(start, booked_start),
min(end, booked_end)
])
self.bookings.append([start, end])
return True
👉 Interview Answer
For My Calendar II, I keep two lists: all bookings and all double-booked intervals.
If a new booking overlaps an existing double-booked interval, it would create a triple booking, so I reject it.
Otherwise, I record any new double-booked intersections with existing bookings and then add the booking.
2️⃣2️⃣ Interval Problems With Min Heap
When Heap Helps
Use a min heap when we need to track active intervals by earliest ending time.
Common examples:
minimum meeting rooms
minimum platforms
maximum concurrent intervals
employee scheduling
Pattern
Sort intervals by start time.
For each interval:
remove inactive intervals from heap
add current interval end to heap
answer may be heap size
Code Skeleton
import heapq
def active_intervals(intervals):
intervals.sort(key=lambda x: x[0])
heap = []
answer = 0
for start, end in intervals:
while heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
answer = max(answer, len(heap))
return answer
👉 Interview Answer
A min heap is useful when I need to know which active interval ends earliest.
I sort intervals by start time.
Before adding the current interval, I remove all intervals that already ended.
Then I push the current end time.
The heap contains active intervals, and its size can represent current concurrency.
2️⃣3️⃣ Interval Problems With Greedy
When Greedy Helps
Greedy often applies when choosing intervals to keep or remove.
Common signals:
minimum removals
maximum non-overlapping intervals
minimum arrows
minimum resources
Common Greedy Rule
Sort by end time.
Choose the interval that ends earliest.
Why?
It leaves maximum room for future intervals.
Examples
Non-overlapping Intervals
Minimum Number of Arrows
Maximum Activity Selection
👉 Interview Answer
Greedy interval problems often sort by end time.
Keeping the interval that ends earliest leaves the most room for future intervals.
This strategy appears in non-overlapping intervals, activity selection, and minimum arrows to burst balloons.
2️⃣4️⃣ Common Edge Cases
Empty Intervals
intervals = []
Return depends on problem:
0
[]
True
Single Interval
Usually already valid.
Touching Boundaries
[1, 3]
[3, 5]
May or may not overlap depending on interval semantics.
For meetings:
no overlap
For merge intervals:
usually merge if inclusive
Same Start Time
[1, 4]
[1, 3]
Sort by end descending may be needed for coverage problems.
Negative Coordinates
Intervals may include negative values.
Sorting still works.
Large Coordinates
Use sweep line sorting instead of large difference arrays.
👉 Interview Answer
Common interval edge cases include empty input, a single interval, touching boundaries, intervals with the same start time, negative coordinates, and very large coordinate ranges.
The most important detail is whether touching intervals should count as overlapping.
2️⃣5️⃣ Common Mistakes
Mistake 1: Wrong Overlap Condition
For half-open intervals:
start < existing_end and existing_start < end
For inclusive intervals:
start <= existing_end and existing_start <= end
Mistake 2: Forgetting to Sort
Many interval problems require sorting before scanning.
Mistake 3: Wrong Tie-Breaking
For sweep line, same-time start and end events need careful ordering.
Mistake 4: Using Merge Logic for Meeting Rooms
Meeting room conflict uses:
current_start < previous_end
not:
current_start <= previous_end
Mistake 5: Difference Array With Huge Coordinates
If coordinates are very large, difference array wastes memory.
Use sweep line instead.
Mistake 6: Sorting Covered Intervals Wrong
For remove covered intervals, sort by:
start ascending, end descending
not just start ascending.
👉 Interview Answer
Common interval mistakes include using the wrong overlap condition, forgetting to sort, mishandling sweep-line tie-breaking, treating touching meeting intervals as conflicts, using difference arrays for huge coordinate ranges, and sorting coverage problems incorrectly.
2️⃣6️⃣ When Interval Pattern Applies
Good Fit
Use interval pattern when the problem asks for:
merge ranges
detect overlap
find gaps
count active intervals
minimum rooms
calendar booking
range coverage
remove overlaps
insert interval
common free time
Problem Signals
Look for words like:
interval
range
start
end
meeting
calendar
booking
overlap
merge
schedule
timeline
active
free time
👉 Interview Answer
I consider interval techniques when the problem involves ranges with start and end times.
Common signals include overlap, merge, meeting rooms, calendar booking, free time, active intervals, and range coverage.
The first question I ask is whether the problem needs sorting, greedy, heap, or sweep line.
2️⃣7️⃣ When Interval Pattern Does Not Apply
Not Good Fit
Interval logic may not be enough when:
need shortest path
need graph reachability
need arbitrary set membership
need dynamic ordered insertion at scale
need multidimensional geometry
Better Alternatives
| Problem Type | Better Pattern |
|---|---|
| Shortest path | BFS / Dijkstra |
| Dynamic calendar at scale | Balanced BST / Segment Tree |
| Static range sum | Prefix Sum |
| Range updates | Difference Array / Segment Tree |
| 2D rectangles | Sweep Line + Data Structure |
| Dependency ordering | Topological Sort |
👉 Interview Answer
Interval sorting handles many one-dimensional range problems.
But if we need dynamic queries at scale, we may need balanced trees or Segment Trees.
If the problem becomes graph reachability, shortest path, or dependency ordering, interval logic alone is not the right tool.
2️⃣8️⃣ Standard Templates
Merge Intervals Template
def merge(intervals):
intervals.sort(key=lambda x: x[0])
result = []
for start, end in intervals:
if not result or result[-1][1] < start:
result.append([start, end])
else:
result[-1][1] = max(result[-1][1], end)
return result
Overlap Check Template
def overlap(a, b):
return a[0] <= b[1] and b[0] <= a[1]
Half-Open Overlap Template
def overlap_half_open(a, b):
return a[0] < b[1] and b[0] < a[1]
Sweep Line Template
def sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end, -1))
events.sort(key=lambda x: (x[0], x[1]))
active = 0
max_active = 0
for time, delta in events:
active += delta
max_active = max(max_active, active)
return max_active
Min Heap Active Intervals Template
import heapq
def max_active(intervals):
intervals.sort(key=lambda x: x[0])
heap = []
answer = 0
for start, end in intervals:
while heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
answer = max(answer, len(heap))
return answer
🧠 Staff-Level Answer Final
👉 Interview Answer Full Version
Interval problems deal with ranges represented by start and end values.
The main questions are usually: do two intervals overlap, can intervals be merged, how many intervals are active at the same time, what gaps exist between intervals, or which intervals should be removed or kept.
The first important detail is interval semantics. For meeting schedules, intervals are usually half-open, meaning a meeting ending at time t does not conflict with another meeting starting at time t. For merge interval problems, boundaries are often treated as inclusive.
Sorting is the most common first step. After sorting by start time, overlapping intervals become adjacent, which allows us to scan from left to right.
For Merge Intervals, I sort by start time, keep a result list, and merge the current interval with the last result interval if they overlap.
For Insert Interval, I divide the scan into three phases: add intervals before the new interval, merge all overlapping intervals, and add intervals after the new interval.
For Meeting Rooms I, I sort by start time and check whether any meeting starts before the previous meeting ends.
For Meeting Rooms II, I need the maximum number of active intervals. I can solve this with a min heap of end times, or with sweep line by sorting all start and end events.
Sweep line converts intervals into events. Start events increase active count, and end events decrease active count. Tie-breaking matters. For half-open intervals, end events should be processed before start events at the same time.
Some interval problems are greedy. For problems like Non-overlapping Intervals or Minimum Arrows, sorting by end time is powerful, because keeping the interval that ends earliest leaves the most room for future intervals.
Difference array is useful when coordinates are small and bounded. It acts like a discrete sweep line: add at the start, subtract at the end, and use prefix sum to compute active values.
At a senior level, I would explain: the interval semantics, the overlap condition, why sorting helps, whether the problem needs merge, greedy, heap, or sweep line, how boundary cases are handled, and why a simpler pattern like prefix sum or a more advanced structure like Segment Tree may be needed in some variants.
⭐ Final Insight
Interval Problems 的核心不是“看到 interval 就 merge”。
它的核心是先判断问题类型：
是 overlap detection， merge ranges， count active intervals， find gaps， remove minimum intervals， 还是 dynamic calendar booking。
Senior-level 的重点是：
interval boundary 是 inclusive 还是 half-open， overlap condition 怎么写， 为什么 sorting by start 或 sorting by end 有不同含义， 什么时候用 heap， 什么时候用 sweep line， 什么时候用 greedy， 什么时候 difference array 或 Segment Tree 更合适。
能讲清楚这些， Interval Problems 就是一类处理 timeline、range、schedule 和 coverage 的核心模式。
中文部分
🎯 Interval Problems
1️⃣ 核心框架
讨论 Interval Problems 时，我通常从：
- Interval problems 是什么
- Interval overlap logic
- Sorting by start time
- Merging intervals
- Insert interval
- Meeting rooms
- Sweep line
- Min heap for active intervals
- Difference array
- 高级工程师解释方式
2️⃣ 要解决什么问题？
Interval problems 处理的是带有 start 和 end 的范围。
它常用于：
- Meeting schedule conflicts
- Calendar booking
- Merge intervals
- Insert interval
- Minimum meeting rooms
- Employee free time
- Airplane count
- Car pooling
- Range coverage
- Event overlap
- Sweep line problems
- CPU task scheduling windows
核心思想是：
一个 interval 表示一个连续 range。
大多数 interval problems 都是在处理 overlap、merge、coverage 或 ordering。
👉 面试回答
Interval problems 是关于 start 和 end 表示的 ranges。
核心问题通常是： 两个 intervals 是否 overlap， intervals 能否 merge， 同一时间有多少 intervals active， 或者 intervals 之间有哪些 gaps。
大多数 interval problems 在 sorting by start time 后会变简单。
3️⃣ Basic Interval Representation
Common Format
Intervals 通常表示为：
[start, end]
Example:
intervals = [[1, 3], [2, 6], [8, 10]]
Meaning
Interval [1, 3] 表示：
从 1 开始
到 3 结束
根据题目不同， end 可能是 inclusive， 也可能是 exclusive。
Important Detail
Meeting problems 通常把 intervals 当成：
[start, end)
这表示：
一个 meeting 在 10 点结束
另一个 meeting 在 10 点开始
它们不冲突
👉 面试回答
Intervals 通常用 start 和 end pair 表示。
一个重要细节是 end boundary 是 inclusive 还是 exclusive。
在 meeting room 问题中， intervals 通常被视为 half-open range， 所以一个 meeting 在 t 结束， 另一个 meeting 在 t 开始， 不算 overlap。
4️⃣ Overlap Logic
Two Intervals
假设有：
a = [a_start, a_end]
b = [b_start, b_end]
如果是 inclusive intervals， 它们 overlap 的条件是：
a_start <= b_end and b_start <= a_end
Non-Overlap Logic
两个 intervals 不 overlap 如果：
a_end < b_start
or
b_end < a_start
对于 meeting rooms 这种 half-open ranges， non-overlap 通常是：
a_end <= b_start
or
b_end <= a_start
Common Merge Condition
按 start time 排序后， current interval 和 previous interval overlap 如果：
current_start <= previous_end
对于 inclusive merge problems。
👉 面试回答
两个 intervals overlap 的本质是： 没有一个 interval 在另一个 interval 开始前已经结束。
排序后， 判断 overlap 就变得很简单： 如果 current start 小于等于 previous end， 那么它们 overlap， 可以 merge。
5️⃣ 为什么 Sorting 有用？
Without Sorting
Intervals 可以是任意顺序：
[8, 10], [1, 3], [2, 6]
很难判断哪些 intervals 应该互相比较。
With Sorting
按 start 排序：
[1, 3], [2, 6], [8, 10]
现在 overlapping intervals 会相邻。
Key Insight
大多数 interval problems 都从这一步开始：
intervals.sort(key=lambda x: x[0])
然后从左到右 scan。
👉 面试回答
Sorting by start time 通常是 interval problems 的第一步。
排序后， overlapping intervals 会变成相邻的 intervals。
这样我们就可以用 previous interval 或 active intervals heap 进行一次扫描。
6️⃣ Merge Intervals
Problem
给定 intervals， merge 所有 overlapping intervals。
Example:
[[1, 3], [2, 6], [8, 10], [15, 18]]
Output:
[[1, 6], [8, 10], [15, 18]]
Idea
先按 start 排序。
维护 result list。
对每个 interval：
如果 result 为空或不 overlap:
append interval
否则:
和最后一个 interval merge
Code
def merge(intervals):
intervals.sort(key=lambda x: x[0])
result = []
for start, end in intervals:
if not result or result[-1][1] < start:
result.append([start, end])
else:
result[-1][1] = max(result[-1][1], end)
return result
👉 面试回答
Merge Intervals 中， 我先按 start time 排序。
然后从左到右扫描。
如果当前 interval 和最后一个 merged interval 不重叠， 就直接加入结果。
否则， 更新最后一个 interval 的 end 为两者 end 的最大值。
7️⃣ Insert Interval
Problem
给定一个 sorted 且 non-overlapping intervals list， 插入一个 new interval， 必要时 merge。
Three Parts
插入 new interval 时分三段处理：
1. new interval 之前的 intervals
2. 和 new interval overlap 的 intervals
3. new interval 之后的 intervals
Code
def insert(intervals, new_interval):
result = []
i = 0
n = len(intervals)
new_start, new_end = new_interval
while i < n and intervals[i][1] < new_start:
result.append(intervals[i])
i += 1
while i < n and intervals[i][0] <= new_end:
new_start = min(new_start, intervals[i][0])
new_end = max(new_end, intervals[i][1])
i += 1
result.append([new_start, new_end])
while i < n:
result.append(intervals[i])
i += 1
return result
👉 面试回答
Insert Interval 可以分三步处理。
第一，加入所有在 new interval 之前结束的 intervals。
第二，merge 所有和 new interval overlap 的 intervals。
第三，加入剩下在 new interval 之后的 intervals。
因为 input 已经 sorted 且 non-overlapping， 所以可以一次扫描完成。
8️⃣ Meeting Rooms
Problem
给定 meeting intervals， 判断一个人是否可以参加所有 meetings。
Key Idea
按 start time 排序。
如果任何 meeting 的 start 早于 previous meeting 的 end， 说明有冲突。
Code
def can_attend_meetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
previous_end = intervals[i - 1][1]
current_start = intervals[i][0]
if current_start < previous_end:
return False
return True
Boundary Note
如果一个 meeting 10 点结束， 另一个 meeting 10 点开始：
[1, 10]
[10, 12]
它们不冲突。
所以判断条件是：
current_start < previous_end
不是：
current_start <= previous_end
👉 面试回答
判断一个人能否参加所有 meetings， 我会先按 start time 排序。
然后比较当前 meeting 和上一个 meeting。
如果当前 meeting 的 start 小于上一个 meeting 的 end， 说明有 overlap， 这个人无法参加所有 meetings。
9️⃣ Meeting Rooms II
Problem
给定 meeting intervals， 返回最少需要多少个 rooms。
Key Idea
需要统计同一时间最多有多少 meetings active。
使用 min heap 存 active meetings 的 end times。
Code
import heapq
def min_meeting_rooms(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[0])
heap = []
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
return len(heap)
Why Heap?
Heap 追踪最早结束的 active meeting。
如果最早结束的 meeting 在当前 meeting 开始前已经结束， 就可以 reuse room。
👉 面试回答
Meeting Rooms II 要求 maximum number of overlapping meetings。
我先按 start time 排序， 然后用 min heap 追踪 active meetings 的 end times。
如果最早结束的 meeting 已经在当前 meeting 开始前结束， 就可以复用这个 room。
否则需要新 room。
Heap size 表示当前需要的 rooms 数量。
🔟 Meeting Rooms II With Sweep Line
Alternative Approach
把 starts 和 ends 分开。
分别排序。
然后用 two pointers。
Code
def min_meeting_rooms(intervals):
starts = sorted(interval[0] for interval in intervals)
ends = sorted(interval[1] for interval in intervals)
rooms = 0
max_rooms = 0
start_pointer = 0
end_pointer = 0
while start_pointer < len(intervals):
if starts[start_pointer] < ends[end_pointer]:
rooms += 1
max_rooms = max(max_rooms, rooms)
start_pointer += 1
else:
rooms -= 1
end_pointer += 1
return max_rooms
Boundary Detail
这里用：
start < end
如果 start 等于 end， 说明之前的 meeting 已经结束， room 可以复用。
👉 面试回答
Meeting Rooms II 也可以用 sweep line。
我把所有 start times 和 end times 分别排序。
当下一个 start 早于下一个 end， 表示有新 meeting 开始， room count 增加。
否则， 一个 meeting 结束， room count 减少。
最大 active count 就是答案。
1️⃣1️⃣ Sweep Line Pattern
Core Idea
Sweep line 把 intervals 转换成 events。
对每个 interval：
start event: +1
end event: -1
然后按 time 排序并扫描。
Example
Intervals:
[1, 3]
[2, 5]
[4, 6]
Events:
(1, +1)
(3, -1)
(2, +1)
(5, -1)
(4, +1)
(6, -1)
排序后：
(1, +1)
(2, +1)
(3, -1)
(4, +1)
(5, -1)
(6, -1)
Code Skeleton
def sweep_line(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end, -1))
events.sort()
active = 0
max_active = 0
for time, delta in events:
active += delta
max_active = max(max_active, active)
return max_active
👉 面试回答
Sweep line 会把 intervals 转换成 start 和 end events。
Start event 增加 active count。 End event 减少 active count。
对 events 按时间排序后， 从左到右扫描， 就能知道每个时间点有多少 intervals active。
1️⃣2️⃣ Sweep Line Tie-Breaking
Why Tie-Breaking Matters
当一个 interval 结束时间等于另一个 interval 开始时间：
[1, 3]
[3, 5]
它们是否 overlap？
对于 meeting rooms：
No
因为 room 可以复用。
Correct Event Order
对于 half-open intervals [start, end)：
end event 应该先于 start event 被处理
所以同一时间：
-1 before +1
Code
def min_rooms_sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end, -1))
events.sort(key=lambda x: (x[0], x[1]))
active = 0
max_active = 0
for time, delta in events:
active += delta
max_active = max(max_active, active)
return max_active
因为 -1 < 1，
所以 end event 会先处理。
👉 面试回答
Sweep line 的 tie-breaking 取决于 interval semantics。
对 meeting intervals， 如果一个 meeting 在 t 结束， 另一个 meeting 在 t 开始， 它们不 overlap。
所以同一 timestamp 下， end event 应该先于 start event 处理。
1️⃣3️⃣ Employee Free Time
Problem
给定所有员工的 schedules， 找出共同 free time intervals。
Idea
把所有 busy intervals flatten 到一个 list。
排序后 merge busy intervals。
Merged intervals 之间的 gaps 就是 common free time。
Code
def employee_free_time(schedule):
intervals = []
for employee in schedule:
for interval in employee:
intervals.append(interval)
intervals.sort(key=lambda x: x[0])
merged = []
for start, end in intervals:
if not merged or merged[-1][1] < start:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
free_time = []
for i in range(1, len(merged)):
previous_end = merged[i - 1][1]
current_start = merged[i][0]
if previous_end < current_start:
free_time.append([previous_end, current_start])
return free_time
👉 面试回答
Employee Free Time 中， 我会把所有员工的 busy intervals flatten 成一个 list。
然后排序并 merge busy intervals。
两个连续 merged busy intervals 之间的 gap， 就是所有人的 common free time。
1️⃣4️⃣ Non-overlapping Intervals
Problem
给定 intervals， 返回最少需要删除多少 intervals， 使剩下 intervals 不重叠。
Greedy Idea
按 end time 排序。
总是保留最早结束的 interval。
这样能给后面的 intervals 留出最多空间。
Code
def erase_overlap_intervals(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[1])
removals = 0
previous_end = intervals[0][1]
for i in range(1, len(intervals)):
start, end = intervals[i]
if start < previous_end:
removals += 1
else:
previous_end = end
return removals
👉 面试回答
Non-overlapping Intervals 中， 我按 end time 排序。
Greedy 地保留最早结束的 interval， 可以给后续 intervals 留出最多空间。
如果下一个 interval 的 start 小于上一个保留 interval 的 end， 它就 overlap，需要删除。
否则保留它，并更新 previous end。
1️⃣5️⃣ Minimum Number of Arrows to Burst Balloons
Problem
每个 balloon 是一个 interval。
一个 arrow 在位置 x 可以打爆所有满足：
start <= x <= end
的 balloons。
返回最少 arrows 数量。
Greedy Idea
按 end 排序。
第一箭射在第一个 balloon 的 end。
如果下一个 balloon 的 start 大于当前 arrow position， 说明需要新 arrow。
Code
def find_min_arrow_shots(points):
if not points:
return 0
points.sort(key=lambda x: x[1])
arrows = 1
arrow_position = points[0][1]
for start, end in points[1:]:
if start > arrow_position:
arrows += 1
arrow_position = end
return arrows
👉 面试回答
这是一道 interval greedy 问题。
我按 end position 排序 balloons。
然后把 arrow 射在最早的 end 上。
如果下一个 balloon 的 start 大于当前 arrow position， 当前 arrow 无法打爆它， 所以需要一支新 arrow。
1️⃣6️⃣ Interval List Intersections
Problem
给定两个 sorted interval lists， 返回它们的 intersections。
Overlap Range
对于两个 intervals：
[a_start, a_end]
[b_start, b_end]
Intersection 是：
[max(a_start, b_start), min(a_end, b_end)]
如果：
start <= end
说明 intersection 有效。
Code
def interval_intersection(first_list, second_list):
i = 0
j = 0
result = []
while i < len(first_list) and j < len(second_list):
start = max(first_list[i][0], second_list[j][0])
end = min(first_list[i][1], second_list[j][1])
if start <= end:
result.append([start, end])
if first_list[i][1] < second_list[j][1]:
i += 1
else:
j += 1
return result
👉 面试回答
Interval List Intersections 中， 两个 input lists 都已经 sorted。
我用 two pointers。
两个 intervals 的 intersection 是 max start 到 min end。
然后移动 end 更早的那个 interval， 因为它不可能再和后面的 intervals 产生交集。
1️⃣7️⃣ Remove Covered Intervals
Problem
删除被其他 intervals 完全覆盖的 intervals。
Interval [a, b] 覆盖 [c, d] 如果：
a <= c and d <= b
Sorting Trick
排序方式：
start ascending
end descending
为什么 end descending？
如果 start 相同， 更长的 interval 要排在前面， 这样才能覆盖短的 interval。
Code
def remove_covered_intervals(intervals):
intervals.sort(key=lambda x: (x[0], -x[1]))
count = 0
max_end = 0
for start, end in intervals:
if end > max_end:
count += 1
max_end = end
return count
👉 面试回答
Remove Covered Intervals 中， 我按 start ascending 和 end descending 排序。
当两个 intervals start 相同时， 更长的 interval 必须先出现， 才能覆盖短的 interval。
然后我追踪目前见过的最远 end。
如果当前 end 没有超过 max_end， 当前 interval 就是被覆盖的。
1️⃣8️⃣ Car Pooling
Problem
每个 trip 是：
[num_passengers, start, end]
判断任意位置是否超过 capacity。
Sweep Line
乘客数量在 pickup 和 dropoff 点发生变化。
start: +passengers
end: -passengers
Code
def car_pooling(trips, capacity):
events = []
for passengers, start, end in trips:
events.append((start, passengers))
events.append((end, -passengers))
events.sort()
current = 0
for location, delta in events:
current += delta
if current > capacity:
return False
return True
👉 面试回答
Car Pooling 可以用 sweep line。
每个 pickup 会增加 passengers。
每个 dropoff 会减少 passengers。
把所有 events 按 location 排序后， 从左到右扫描， 检查 active passengers 是否超过 capacity。
1️⃣9️⃣ Difference Array for Range Changes
When Coordinates Are Small
如果 coordinate range 很小， difference array 比 sort events 更简单。
Idea
对于 interval update [start, end)：
diff[start] += value
diff[end] -= value
然后 prefix sum 得到每个 point 的 active count。
Code
def car_pooling(trips, capacity):
diff = [0] * 1001
for passengers, start, end in trips:
diff[start] += passengers
diff[end] -= passengers
current = 0
for change in diff:
current += change
if current > capacity:
return False
return True
👉 面试回答
Difference array 适合 coordinates 小且 bounded 的 interval 问题。
对每个 range， 在 start 加上变化值， 在 end 减去变化值。
然后 prefix scan 就能得到每个位置的 active value。
它本质上是一个离散版本的 sweep line。
2️⃣0️⃣ Calendar Booking
Problem
实现一个 calendar， 如果新 booking 不和已有 bookings overlap， 就成功预订。
Simple Approach
每次新 booking， 和所有 existing bookings 检查 overlap。
两个 half-open intervals overlap 如果：
start < existing_end and existing_start < end
Code
class MyCalendar:
def __init__(self):
self.bookings = []
def book(self, start, end):
for existing_start, existing_end in self.bookings:
if start < existing_end and existing_start < end:
return False
self.bookings.append([start, end])
return True
👉 面试回答
My Calendar I 中， 我存所有 existing bookings。
每次新 booking， 检查它是否和任何 existing interval overlap。
对 half-open intervals， 两个 bookings overlap 的条件是： start 小于 existing end， 并且 existing start 小于 end。
如果没有 overlap， 就加入 booking。
2️⃣1️⃣ My Calendar II
Problem
允许 double booking， 但不允许 triple booking。
Idea
维护两个 list：
booked intervals
overlapped intervals
对每个新 interval：
如果它和任何 existing overlap interval overlap:
会形成 triple booking
否则， 记录它和 existing booked intervals 产生的新 overlaps。
Code
class MyCalendarTwo:
def __init__(self):
self.bookings = []
self.overlaps = []
def book(self, start, end):
for overlap_start, overlap_end in self.overlaps:
if start < overlap_end and overlap_start < end:
return False
for booked_start, booked_end in self.bookings:
if start < booked_end and booked_start < end:
self.overlaps.append([
max(start, booked_start),
min(end, booked_end)
])
self.bookings.append([start, end])
return True
👉 面试回答
My Calendar II 中， 我维护两个 lists： 所有 bookings， 以及所有 double-booked intervals。
如果一个 new booking 和已有 double-booked interval overlap， 就会产生 triple booking， 所以要 reject。
否则， 把它和已有 bookings 产生的新 double-booked intersections 记录下来， 然后加入 booking。
2️⃣2️⃣ Interval Problems With Min Heap
When Heap Helps
当我们需要根据最早结束时间追踪 active intervals 时， min heap 很有用。
常见例子：
minimum meeting rooms
minimum platforms
maximum concurrent intervals
employee scheduling
Pattern
按 start time 排序。
对每个 interval：
remove inactive intervals from heap
add current interval end to heap
answer may be heap size
Code Skeleton
import heapq
def active_intervals(intervals):
intervals.sort(key=lambda x: x[0])
heap = []
answer = 0
for start, end in intervals:
while heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
answer = max(answer, len(heap))
return answer
👉 面试回答
当我需要知道 active intervals 中哪个最早结束时， min heap 很适合。
我先按 start time 排序。
在加入 current interval 前， 先移除所有已经结束的 intervals。
然后把当前 end time 加入 heap。
Heap 中保存的是当前 active intervals， heap size 可以表示当前 concurrency。
2️⃣3️⃣ Interval Problems With Greedy
When Greedy Helps
当问题是选择保留或删除 intervals 时， greedy 经常适用。
常见信号：
minimum removals
maximum non-overlapping intervals
minimum arrows
minimum resources
Common Greedy Rule
按 end time 排序。
选择最早结束的 interval。
原因是：
It leaves maximum room for future intervals.
Examples
Non-overlapping Intervals
Minimum Number of Arrows
Maximum Activity Selection
👉 面试回答
Greedy interval problems 经常按 end time 排序。
保留最早结束的 interval， 可以给后续 intervals 留出最多空间。
这个策略常见于 non-overlapping intervals、 activity selection， 以及 minimum arrows to burst balloons。
2️⃣4️⃣ 常见 Edge Cases
Empty Intervals
intervals = []
返回值取决于题目：
0
[]
True
Single Interval
通常已经 valid。
Touching Boundaries
[1, 3]
[3, 5]
是否 overlap 取决于题目语义。
对于 meetings：
no overlap
对于 merge intervals：
通常 inclusive 情况下会 merge
Same Start Time
[1, 4]
[1, 3]
Coverage problems 可能需要 end descending。
Negative Coordinates
Intervals 可能包含负数。
Sorting 仍然适用。
Large Coordinates
Coordinates 很大时， 不要使用巨大 difference array， 应该用 sweep line sorting。
👉 面试回答
Interval 常见 edge cases 包括 empty input、 single interval、 touching boundaries、 same start time、 negative coordinates， 以及 very large coordinate ranges。
最重要的是弄清楚 touching intervals 是否算 overlap。
2️⃣5️⃣ 常见错误
Mistake 1: Overlap Condition 写错
Half-open intervals:
start < existing_end and existing_start < end
Inclusive intervals:
start <= existing_end and existing_start <= end
Mistake 2: 忘记 Sort
很多 interval problems 都需要先排序再扫描。
Mistake 3: Tie-Breaking 错误
Sweep line 中， 同一时间 start 和 end events 的顺序要谨慎处理。
Mistake 4: Meeting Rooms 使用了 Merge 的条件
Meeting room conflict 应该是：
current_start < previous_end
不是：
current_start <= previous_end
Mistake 5: Huge Coordinates 仍用 Difference Array
如果 coordinates 很大， difference array 会浪费大量内存。
应该用 sweep line。
Mistake 6: Covered Intervals 排序错误
Remove Covered Intervals 应该排序为：
start ascending, end descending
不是只按 start ascending。
👉 面试回答
Interval 常见错误包括： overlap condition 写错、 忘记 sort、 sweep-line tie-breaking 处理错误、 把 touching meeting intervals 当成 conflict、 对 huge coordinates 使用 difference array， 以及 covered intervals 的排序方式错误。
2️⃣6️⃣ 什么时候 Interval Pattern 适用？
Good Fit
当题目问：
merge ranges
detect overlap
find gaps
count active intervals
minimum rooms
calendar booking
range coverage
remove overlaps
insert interval
common free time
Problem Signals
看到这些关键词想到 Interval Pattern：
interval
range
start
end
meeting
calendar
booking
overlap
merge
schedule
timeline
active
free time
👉 面试回答
当问题涉及 start 和 end 表示的 ranges 时， 我会考虑 interval techniques。
常见信号包括 overlap、merge、meeting rooms、 calendar booking、free time、active intervals， 以及 range coverage。
我会先判断这个题需要 sorting、greedy、heap 还是 sweep line。
2️⃣7️⃣ 什么时候 Interval Pattern 不适用？
Not Good Fit
Interval logic 不一定适合：
need shortest path
need graph reachability
need arbitrary set membership
need dynamic ordered insertion at scale
need multidimensional geometry
Better Alternatives
| Problem Type | Better Pattern |
|---|---|
| Shortest path | BFS / Dijkstra |
| Dynamic calendar at scale | Balanced BST / Segment Tree |
| Static range sum | Prefix Sum |
| Range updates | Difference Array / Segment Tree |
| 2D rectangles | Sweep Line + Data Structure |
| Dependency ordering | Topological Sort |
👉 面试回答
Interval sorting 可以处理很多一维 range problems。
但是如果需要 scale 下的 dynamic queries， 可能需要 balanced tree 或 Segment Tree。
如果问题变成 graph reachability、shortest path， 或 dependency ordering， interval logic 本身就不是正确工具。
2️⃣8️⃣ 标准模板
Merge Intervals Template
def merge(intervals):
intervals.sort(key=lambda x: x[0])
result = []
for start, end in intervals:
if not result or result[-1][1] < start:
result.append([start, end])
else:
result[-1][1] = max(result[-1][1], end)
return result
Overlap Check Template
def overlap(a, b):
return a[0] <= b[1] and b[0] <= a[1]
Half-Open Overlap Template
def overlap_half_open(a, b):
return a[0] < b[1] and b[0] < a[1]
Sweep Line Template
def sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1))
events.append((end, -1))
events.sort(key=lambda x: (x[0], x[1]))
active = 0
max_active = 0
for time, delta in events:
active += delta
max_active = max(max_active, active)
return max_active
Min Heap Active Intervals Template
import heapq
def max_active(intervals):
intervals.sort(key=lambda x: x[0])
heap = []
answer = 0
for start, end in intervals:
while heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
answer = max(answer, len(heap))
return answer
🧠 Staff-Level Answer Final
👉 面试回答完整版本
Interval problems 处理的是由 start 和 end 表示的 ranges。
核心问题通常包括： 两个 intervals 是否 overlap， intervals 是否可以 merge， 同一时间有多少 intervals active， intervals 之间有哪些 gaps， 或者应该保留/删除哪些 intervals。
第一个重要细节是 interval semantics。 对 meeting schedules， intervals 通常是 half-open， 也就是一个 meeting 在 time t 结束， 另一个 meeting 在 time t 开始， 它们不冲突。 对 merge intervals， boundaries 通常按 inclusive 处理。
Sorting 是最常见的第一步。 按 start time 排序后， overlapping intervals 会相邻， 这样就可以从左到右扫描。
对 Merge Intervals， 我按 start time 排序， 维护 result list， 如果 current interval 和 result 中最后一个 interval overlap， 就 merge。
对 Insert Interval， 我把扫描分成三段： 加入 new interval 前面的 intervals， merge 所有和 new interval overlap 的 intervals， 最后加入 new interval 后面的 intervals。
对 Meeting Rooms I， 我按 start time 排序， 检查是否有 meeting 的 start 小于 previous meeting 的 end。
对 Meeting Rooms II， 我需要 maximum active intervals。 可以用 min heap 存 active meeting end times， 也可以用 sweep line 排序所有 start 和 end events。
Sweep line 会把 intervals 转换成 events。 Start event 增加 active count， end event 减少 active count。 Tie-breaking 很重要。 对 half-open intervals， 同一时间 end event 应该先于 start event 处理。
有些 interval problems 是 greedy。 例如 Non-overlapping Intervals 或 Minimum Arrows， 按 end time 排序很有用， 因为保留最早结束的 interval， 可以给后续 intervals 留出最多空间。
Difference array 适合 coordinates 小且 bounded 的问题。 它本质上是一个离散 sweep line： 在 start 加， 在 end 减， 然后用 prefix sum 得到 active value。
高级工程师解释 interval problems 时， 我会讲清楚： interval semantics， overlap condition， 为什么 sorting 有用， 这个题需要 merge、greedy、heap 还是 sweep line， boundary cases 如何处理， 以及什么时候需要 prefix sum、difference array 或 Segment Tree 这样的替代方案。
⭐ Final Insight
Interval Problems 的核心不是“看到 interval 就 merge”。
它的核心是先判断问题类型：
是 overlap detection， merge ranges， count active intervals， find gaps， remove minimum intervals， 还是 dynamic calendar booking。
Senior-level 的重点是：
interval boundary 是 inclusive 还是 half-open， overlap condition 怎么写， sorting by start 和 sorting by end 分别代表什么， 什么时候用 heap， 什么时候用 sweep line， 什么时候用 greedy， 什么时候 difference array 或 Segment Tree 更合适。
能讲清楚这些， Interval Problems 就是一类处理 timeline、range、schedule 和 coverage 的核心模式。
Implement