区间问题 Interval Problems

interval problemssweep lineLeetCodealgorithminterview

区间问题 Interval Problems

区间问题是算法中的一个重要类型，涉及区间的合并、重叠检测、调度等。本指南涵盖常见的区间问题类型及其解决方案。

基础概念 Basic Concepts

1. 区间表示 Interval Representation

class Interval:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end

2. 区间关系 Interval Relationships

  • 重叠 (Overlap)
  • 包含 (Contain)
  • 相邻 (Adjacent)
  • 分离 (Disjoint)

常见问题类型 Common Problem Types

1. 区间合并 Merge Intervals

def mergeIntervals(intervals: List[Interval]) -> List[Interval]:
    if not intervals:
        return []
    
    # 按开始时间排序
    intervals.sort(key=lambda x: x.start)
    
    result = [intervals[0]]
    for interval in intervals[1:]:
        if interval.start <= result[-1].end:
            # 合并重叠区间
            result[-1].end = max(result[-1].end, interval.end)
        else:
            result.append(interval)
    
    return result

2. 插入区间 Insert Interval

def insertInterval(intervals: List[Interval], newInterval: Interval) -> List[Interval]:
    result = []
    i = 0
    n = len(intervals)
    
    # 添加所有在新区间之前的区间
    while i < n and intervals[i].end < newInterval.start:
        result.append(intervals[i])
        i += 1
    
    # 合并重叠的区间
    while i < n and intervals[i].start <= newInterval.end:
        newInterval.start = min(newInterval.start, intervals[i].start)
        newInterval.end = max(newInterval.end, intervals[i].end)
        i += 1
    
    result.append(newInterval)
    
    # 添加剩余的区间
    while i < n:
        result.append(intervals[i])
        i += 1
    
    return result

3. 区间重叠检测 Interval Overlap Detection

def hasOverlap(intervals: List[Interval]) -> bool:
    if not intervals:
        return False
    
    intervals.sort(key=lambda x: x.start)
    for i in range(1, len(intervals)):
        if intervals[i].start <= intervals[i-1].end:
            return True
    
    return False

高级技巧 Advanced Techniques

1. 扫描线算法 Sweep Line Algorithm

def countMaxOverlap(intervals: List[Interval]) -> int:
    events = []
    # 将每个区间拆分为开始和结束事件
    for interval in intervals:
        events.append((interval.start, 1))  # 1表示开始
        events.append((interval.end, -1))   # -1表示结束
    
    events.sort()  # 按时间排序
    
    current = 0
    max_overlap = 0
    for time, delta in events:
        current += delta
        max_overlap = max(max_overlap, current)
    
    return max_overlap

2. 差分数组 Difference Array

def handleRangeUpdates(n: int, updates: List[List[int]]) -> List[int]:
    diff = [0] * (n + 1)
    
    # 处理区间更新
    for start, end, val in updates:
        diff[start] += val
        diff[end + 1] -= val
    
    # 还原原数组
    result = [0] * n
    curr = 0
    for i in range(n):
        curr += diff[i]
        result[i] = curr
    
    return result

实际应用 Practical Applications

1. 会议室安排 Meeting Rooms

def minMeetingRooms(intervals: List[Interval]) -> int:
    if not intervals:
        return 0
    
    # 分别提取开始和结束时间
    starts = sorted(i.start for i in intervals)
    ends = sorted(i.end for i in intervals)
    
    rooms = 0
    max_rooms = 0
    s = e = 0
    
    while s < len(intervals):
        if starts[s] < ends[e]:
            rooms += 1
            s += 1
        else:
            rooms -= 1
            e += 1
        max_rooms = max(max_rooms, rooms)
    
    return max_rooms

2. 任务调度 Task Scheduling

def canScheduleTasks(tasks: List[Interval]) -> bool:
    tasks.sort(key=lambda x: x.end)  # 按结束时间排序
    
    last_end = float('-inf')
    for task in tasks:
        if task.start < last_end:
            return False
        last_end = task.end
    
    return True

经典题目 Classic Problems

1. 合并区间 (56. Merge Intervals)

  • 排序后合并重叠区间
  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(n)

2. 插入区间 (57. Insert Interval)

  • 三步处理：前、中、后
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

3. 会议室 II (253. Meeting Rooms II)

  • 使用扫描线或优先队列
  • 时间复杂度: O(nlogn)
  • 空间复杂度: O(n)

4. 区间列表的交集 (986. Interval List Intersections)

  • 双指针技巧
  • 时间复杂度: O(n+m)
  • 空间复杂度: O(n+m)

解题技巧 Problem-Solving Tips

  1. 区间排序

    • 按开始时间排序
    • 按结束时间排序
    • 根据具体问题选择

  2. 重叠判断

    • start1 <= end2 && start2 <= end1
    • 使用扫描线处理多区间

  3. 区间合并

    • 排序后线性扫描
    • 维护当前合并区间

  4. 特殊情况处理

    • 空区间
    • 单个区间
    • 完全重叠的区间

常见错误 Common Mistakes

  1. 排序选择错误

    • 未考虑是否需要排序
    • 排序标准选择不当

  2. 边界处理不当

    • 区间开闭性未统一
    • 相邻区间判断错误

  3. 更新逻辑错误

    • 合并时未更新正确的边界
    • 忘记处理剩余区间

  4. 效率问题

    • 未使用适当的数据结构
    • 算法复杂度不是最优

练习建议 Practice Suggestions

  1. 基础练习

    • 从简单的区间合并开始
    • 掌握重叠检测的基本方法

  2. 进阶练习

    • 尝试使用扫描线算法
    • 解决复杂的调度问题

  3. 实战应用

    • 会议室分配
    • 任务调度优化

  4. 优化技巧

    • 考虑时间和空间效率
    • 尝试不同的解决方案

参考资源 References

  1. 区间问题精讲
  2. 扫描线算法详解
  3. 区间调度算法