会议安排、任务调度、时间管理——区间问题是现实世界最直接的算法应用
区间问题通常以 [start, end] 形式给出，涉及区间的合并、插入、删除、重叠判断等操作。解题的万能第一步：按起点或终点排序，排序后问题往往变得简单。
# 区间排序
intervals.sort(key=lambda x: x[0]) # 按起点
intervals.sort(key=lambda x: x[1]) # 按终点
# 判断两个区间是否重叠
def is_overlap(a, b):
return a[0] <= b[1] and b[0] <= a[1]
# 合并两个重叠区间
def merge_two(a, b):
return [min(a[0], b[0]), max(a[1], b[1])]题目描述：给定一组区间，合并所有重叠的区间。
[cur_start, cur_end]。遍历每个新区间，如果新区间起点 ≤ 当前终点（重叠），则合并（更新终点）；否则，保存当前区间，开始新区间。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
result = [intervals[0]]
for interval in intervals[1:]:
# 重叠 → 合并
if interval[0] <= result[-1][1]:
result[-1][1] = max(result[-1][1], interval[1])
else:
result.append(interval)
return result时间复杂度：O(n log n) — 排序主导
空间复杂度：O(n) — 结果数组
max(result[-1][1], interval[1]) 而非直接用 interval[1]，因为可能存在 [1,5],[2,3] 这种被包含的情况。题目描述：给定一个无重叠的有序区间列表和一个新区间，插入新区间并合并重叠部分。
class Solution:
def insert(self, intervals: List[List[int]],
newInterval: List[int]) -> List[List[int]]:
result = []
i = 0
n = len(intervals)
# 阶段1: 完全在左侧的
while i < n and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# 阶段2: 重叠的，合并
while i < n and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# 阶段3: 完全在右侧的
while i < n:
result.append(intervals[i])
i += 1
return result时间复杂度：O(n) — 有序区间，一次遍历
空间复杂度：O(n)
题目描述：给定一组区间，找到需要移除的最小区间数，使剩余区间互不重叠。
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if not intervals:
return 0
# 按终点排序
intervals.sort(key=lambda x: x[1])
count = 0 # 需要删除的数量
end = intervals[0][1]
for i in range(1, len(intervals)):
if intervals[i][0] < end:
# 重叠，删除当前区间
count += 1
else:
# 不重叠，保留，更新终点
end = intervals[i][1]
return count时间复杂度：O(n log n) — 排序
空间复杂度：O(1)
区间问题有一套固定的解题范式：
# 区间问题通用框架
def solve_intervals(intervals):
intervals.sort(key=lambda x: x[0]) # 或 x[1]
result = [intervals[0]] # 或其他初始值
for interval in intervals[1:]:
if has_overlap(result[-1], interval):
# 处理重叠：合并 or 删除
handle_overlap(result, interval)
else:
# 不重叠：直接加入
result.append(interval)
return result对于"某点被多少区间覆盖"的问题，用扫描线：将每个区间的起止点标记为 +1/-1 事件，排序后扫描。
# 扫描线: 求最多同时有多少区间重叠
def min_meeting_rooms(intervals):
events = []
for start, end in intervals:
events.append((start, 1)) # 开始+1
events.append((end, -1)) # 结束-1
events.sort()
cur = max_rooms = 0
for _, delta in events:
cur += delta
max_rooms = max(max_rooms, cur)
return max_rooms对于区间加减、区间查询的问题，差分数组可以在 O(1) 完成区间修改，O(n) 完成前缀和还原。
# 差分数组: 区间[l,r]全部+val
diff = [0] * (n + 1)
diff[l] += val
diff[r + 1] -= val
# 还原: 前缀和
arr = [0] * n
arr[0] = diff[0]
for i in range(1, n):
arr[i] = arr[i-1] + diff[i]