区间调度与合并
通过按结束时间排序解决会议室和无重叠区间问题，并通过按开始时间排序解决区间合并问题。
区间调度与合并 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
区间问题概览
区间问题经常出现在调度、日历管理和资源分配类面试中。关键模式包括：合并重叠区间、计算最少会议室数量、寻找最大的互不重叠区间集合以及插入新区间。大多数区间问题都从同一个步骤开始：按开始 time（或根据问题要求按结束 time）对区间进行 sort。选择正确的排序关键字通常是最困难的部分。
# Intervals: each = [start, end] (inclusive or exclusive by problem)
# Example:
intervals = [[1,3],[2,6],[8,10],[15,18]]
# Sorted by start (already sorted here)
# Visually:
# [1,3] |-|
# [2,6] |---|
# [8,10] |--|
# [15,18] |---|
print('Intervals ready for analysis')合并重叠区间
合并区间（LeetCode 56）：给定一个区间列表，合并所有重叠区间。算法：按开始 time 进行 sort。遍历排序后的列表；如果当前区间与最后一个合并区间重叠（其开始 ≤ 最后一个合并区间的 end），就将最后一个合并区间的 end 扩展为两者 end 中的最大值。否则，将当前区间 append 为新的合并区间。Time：sort 的复杂度为 O(n log n)，合并的复杂度为 O(n)。
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
# Overlapping: extend the last interval
merged[-1][1] = max(last_end, end)
else:
# Non-overlapping: add as new interval
merged.append([start, end])
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))
# [[1,5]] (touching intervals merge)插入区间
插入区间（LeetCode 57）：给定一个已排序且互不重叠的区间列表，插入新区间并重新合并。遍历过程分为三个阶段：(1) add 所有在新区间开始前结束的区间。(2) 合并所有与新区间重叠的区间（扩展新区间的边界）。(3) 加入所有剩余区间。在本题中，排序已经完成，因此这是排序 O(n log n) 之后的一次 O(n) 遍历。
def insert_interval(intervals, new_interval):
result = []
i = 0
n = len(intervals)
# Phase 1: intervals before new_interval
while i < n and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge 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: remaining intervals
while i < n:
result.append(intervals[i])
i += 1
return result
print(insert_interval([[1,3],[6,9]], [2,5])) # [[1,5],[6,9]]
print(insert_interval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
# [[1,2],[3,10],[12,16]]会议室 I：能参加所有会议吗
会议室 I（LeetCode 252）：给定会议时间区间，判断一个人能否参加所有会议。按开始 time 进行 sort；如果某个会议在前一个会议结束前开始，就说明它们重叠。这是最简单的区间检查问题——总复杂度为 O(n log n)。关键洞察是：排序后，只需比较相邻的区间对。
def can_attend_meetings(intervals):
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
# Current meeting starts before previous ends?
if intervals[i][0] < intervals[i-1][1]:
return False
return True
print(can_attend_meetings([[0,30],[5,10],[15,20]])) # False (0,30 overlaps 5,10)
print(can_attend_meetings([[7,10],[2,4]])) # True (4 < 7, no overlap)会议室 II：最少会议室
会议室 II（LeetCode 253）：找出同时容纳所有会议所需的最少会议室数量。使用最小堆跟踪最早结束的会议室。按开始 time 对会议进行 sort。对于每个新会议：如果它在最早结束的会议室的 end 之后开始，就重新使用该会议室（执行 pop，再推入新结束 time）；否则，打开一个新会议室。最后的堆大小就是所需的会议室数量。
import heapq
def min_meeting_rooms(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[0]) # sort by start
heap = [] # min-heap of end times
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heapreplace(heap, end) # reuse earliest-ending room
else:
heapq.heappush(heap, end) # open a new room
return len(heap)
print(min_meeting_rooms([[0,30],[5,10],[15,20]])) # 2
print(min_meeting_rooms([[7,10],[2,4]])) # 1
print(min_meeting_rooms([[9,10],[4,9],[4,17]])) # 2统计会议室数量的扫描线替代方法
另一种 O(n log n) 方法是扫描线。为每个区间的开始和结束创建事件，分别记为 (+1) 和 (-1)。按 time 对所有事件进行排序（如果区间不包含端点，相同 time 时让 end 排在 start 前）。从左到右扫描，同时维护当前活跃会议的数量。最大数量就是所需的最少会议室数。对于某些人来说，这种方法更直观，而且可以推广到其他区间计数问题。
def min_rooms_sweep(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # meeting starts
events.append((end, -1)) # meeting ends
# Sort: same time → end (-1) before start (1) if exclusive
events.sort(key=lambda x: (x[0], x[1]))
max_rooms = current = 0
for _, delta in events:
current += delta
max_rooms = max(max_rooms, current)
return max_rooms
print(min_rooms_sweep([[0,30],[5,10],[15,20]])) # 2
print(min_rooms_sweep([[1,5],[2,6],[3,7]])) # 3 (all overlap at t=3)不重叠区间：最大选择
不重叠区间（LeetCode 435）：找出需要 remove 的最少区间数量，使剩余区间互不重叠。这等价于寻找最多的不重叠区间数量（活动选择问题），然后将其余区间作为移除数量返回。按 end time 进行排序：贪心地保留最早结束的区间（为后续区间最大限度地保留空间）。当下一个区间发生重叠时，discard 它，并将移除数量加一。
def erase_overlap_intervals(intervals):
if not intervals: return 0
intervals.sort(key=lambda x: x[1]) # sort by END time
removals = 0
last_end = float('-inf')
for start, end in intervals:
if start >= last_end:
last_end = end # keep this interval
else:
removals += 1 # remove this interval (it overlaps)
return removals
print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]])) # 1 (remove [1,3])
print(erase_overlap_intervals([[1,2],[1,2],[1,2]])) # 2
print(erase_overlap_intervals([[1,2],[2,3]])) # 0 (no overlap)为什么按结束时间而不是开始时间排序
对于活动选择问题（最大不重叠集合），按结束时间排序已被证明是最优的。直觉是：越早结束的活动，就越能为后续活动留出空间。如果按开始时间排序，我们可能会选中一个很早开始但持续时间很长的活动，从而阻挡许多更晚开始的短活动。交换论证：如果最优解选择了活动 A 而不是最早结束的 G，就用 G 替换 A——G 不会比 A 更晚结束，因此凡是与 A 不冲突的活动，也都不会与 G 冲突。
# Counterexample for sorting by START time:
# [[1,10],[2,3],[4,5]] — sorted by start: [1,10],[2,3],[4,5]
# Sort-by-start greedy keeps [1,10], can't add [2,3] or [4,5] (all overlap [1,10])
# Selects: 1 interval
# Sort-by-end greedy:
# [[2,3],[4,5],[1,10]] — sorted by end
# Keep [2,3] (end=3), then [4,5] (start=4 >= 3, keep), then [1,10] (start=1 < 5, skip)
# Selects: 2 intervals — OPTIMAL
intervals = [[1,10],[2,3],[4,5]]
intervals.sort(key=lambda x: x[1])
last_end = float('-inf')
count = 0
for s, e in intervals:
if s >= last_end:
count += 1; last_end = e
print('Max non-overlapping:', count) # 2区间列表交集
区间列表交集（LeetCode 986）：从两个已排序的区间列表中找出所有相交的区间对。使用双指针方法。每一步都计算当前区间对的交集（起点的最大值，终点的最小值）。如果起点 ≤ 终点，则交集有效。然后将结束更早的那个区间对应的指针向前移动。时间复杂度为 O(m+n)。
def interval_intersection(A, B):
result = []
i = j = 0
while i < len(A) and j < len(B):
# Intersection boundaries
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
result.append([lo, hi]) # valid intersection
# Advance pointer of interval that ends first
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return result
A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(interval_intersection(A, B))
# [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]划分字母区间
划分字母区间（LeetCode 763）：将字符串划分为尽可能多的部分，使每个字符最多只出现在一个部分中。贪心做法是：对于每个字符，找到它最后一次出现的位置。遍历字符串，同时维护 max_end。当 i == max_end 时，当前区间完成——记录其长度，并开始新的区间。这本质上是一个区间合并问题。
def partition_labels(s):
last = {c: i for i, c in enumerate(s)} # last occurrence of each char
partitions = []
start = max_end = 0
for i, c in enumerate(s):
max_end = max(max_end, last[c])
if i == max_end: # partition complete
partitions.append(max_end - start + 1)
start = i + 1
return partitions
print(partition_labels('ababcbacadefegdehijhklij'))
# [9, 7, 8] — parts 'ababcbaca', 'defegde', 'hijhklij'区间问题总结
掌握区间问题的以下四种模式：（1）合并：按开始时间排序，发生重叠时延长最后一个区间。（2）统计房间数：按开始时间排序，使用以结束时间为键的最小堆。（3）最大不重叠数量：按结束时间排序并进行贪心选择。（4）插入：三阶段线性扫描。排序关键字很重要：合并使用开始时间，最大数量选择使用结束时间。时间复杂度始终为 O(n log n)，主要由排序决定；合并和扫描为 O(n)。
# Quick reference:
# Merge intervals: sort by start, extend if overlap
# Insert interval: three-phase linear scan
# Meeting rooms (can?): sort by start, check consecutive overlap
# Meeting rooms (min?): sort by start, min-heap of end times / sweep
# Max non-overlapping: sort by END, greedy keep
# Min removals: n - max_non_overlapping
# Interval intersection: two pointers on sorted lists
print('Pattern: sort key is the decisive choice')
print('Merge → sort by start')
print('Activity selection → sort by end')
print('Room count → sort by start + heap of ends')快速检查
测试您对本课中数据结构与算法 & 编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：通过按开始时间排序，并在发生重叠时延长最后一个区间来合并区间、最少会议室数量问题使用按开始时间排序加上按结束时间排列的最小堆，在最早结束的房间空闲后复用该房间，以及最大不重叠区间问题使用按结束时间排序的贪心选择。接下来我们将学习跳跃游戏 I 和 II——通过贪心扩展可达范围来解决可达性和最少跳跃次数问题。
常见问题解答
「区间调度与合并」课时是免费的吗？
是的 — 「区间调度与合并」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「区间调度与合并」这节课中我会学到什么？
通过按结束时间排序解决会议室和无重叠区间问题，并通过按开始时间排序解决区间合并问题。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「区间调度与合并」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。