贪心算法1：区间调度问题

引言

贪心算法(Greedy Algorithm)是一种在每一步选择中都采取当前最优解的算法策略。它的核心思想是在求解过程中，始终做出当前看来最好的选择，希望通过局部最优选择达到全局最优的结果。

区间调度问题是学习贪心算法的经典入门题型，它能够很好地展示贪心算法的精髓和应用场景。

问题描述

问题定义：给定若干个区间，选择尽可能多的区间，使得这些区间互不重叠。

例如：

• 区间集合：[[1,3], [2,6], [8,10], [15,18]]
• 最优解：选择 [1,3], [8,10], [15,18]，共3个区间

贪心策略分析

对于区间调度问题，我们可能会考虑以下几种贪心策略：

策略1：选择起始时间最早的区间

反例：[[1,100], [2,3], [4,5]]

• 贪心选择：[1,100]
• 最优解：[2,3], [4,5]
• 结论：此策略不可行

策略2：选择持续时间最短的区间

反例：[[1,2], [2,100], [3,4]]

• 贪心选择：[1,2], [3,4]
• 但如果有 [[1,2], [1.5,2.5], [2,3]]，最短区间策略可能不是最优

策略3：选择结束时间最早的区间 ✓

这是正确的贪心策略！

证明思路：

• 设最优解为 OPT，贪心解为 GREEDY
• 假设贪心算法选择的第一个区间 g₁ 不在 OPT 中
• 设 OPT 中第一个区间为 o₁
• 由于 g₁.end ≤ o₁.end，我们可以用 g₁ 替换 o₁
• 递归证明后续选择的正确性

算法实现

Java实现

import java.util.*;

public class IntervalScheduling {
    
    public static class Interval {
        int start, end;
        
        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
        
        @Override
        public String toString() {
            return "[" + start + "," + end + "]";
        }
    }
    
    /**
     * 区间调度问题 - 贪心算法
     * @param intervals 区间数组
     * @return 最大不重叠区间数量
     */
    public static int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length <= 1) return 0;
        
        // 按结束时间排序
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        
        int count = 1;  // 至少选择一个区间
        int end = intervals[0][1];  // 当前选择区间的结束时间
        
        for (int i = 1; i < intervals.length; i++) {
            // 如果当前区间的开始时间 >= 上一个选择区间的结束时间
            if (intervals[i][0] >= end) {
                count++;
                end = intervals[i][1];
            }
        }
        
        return intervals.length - count;  // 返回需要删除的区间数
    }
    
    /**
     * 返回具体的调度方案
     */
    public static List<Interval> findMaxIntervals(int[][] intervals) {
        if (intervals.length == 0) return new ArrayList<>();
        
        // 转换为Interval对象并按结束时间排序
        List<Interval> list = new ArrayList<>();
        for (int[] interval : intervals) {
            list.add(new Interval(interval[0], interval[1]));
        }
        list.sort((a, b) -> a.end - b.end);
        
        List<Interval> result = new ArrayList<>();
        result.add(list.get(0));
        
        for (int i = 1; i < list.size(); i++) {
            Interval current = list.get(i);
            Interval last = result.get(result.size() - 1);
            
            if (current.start >= last.end) {
                result.add(current);
            }
        }
        
        return result;
    }
}

Python实现

def erase_overlap_intervals(intervals):
    """
    区间调度问题 - 贪心算法
    :param intervals: List[List[int]] 区间列表
    :return: int 需要删除的最少区间数
    """
    if len(intervals) <= 1:
        return 0
    
    # 按结束时间排序
    intervals.sort(key=lambda x: x[1])
    
    count = 1  # 至少选择一个区间
    end = intervals[0][1]  # 当前选择区间的结束时间
    
    for i in range(1, len(intervals)):
        # 如果当前区间的开始时间 >= 上一个选择区间的结束时间
        if intervals[i][0] >= end:
            count += 1
            end = intervals[i][1]
    
    return len(intervals) - count

def find_max_intervals(intervals):
    """
    返回具体的最优调度方案
    """
    if not intervals:
        return []
    
    # 按结束时间排序
    intervals.sort(key=lambda x: x[1])
    
    result = [intervals[0]]
    
    for i in range(1, len(intervals)):
        if intervals[i][0] >= result[-1][1]:
            result.append(intervals[i])
    
    return result

# 测试用例
if __name__ == "__main__":
    # 测试用例1
    intervals1 = [[1,2], [2,3], [3,4], [1,3]]
    print(f"输入: {intervals1}")
    print(f"需要删除的区间数: {erase_overlap_intervals(intervals1)}")
    print(f"最优方案: {find_max_intervals(intervals1)}")
    print()
    
    # 测试用例2
    intervals2 = [[1,2], [1,2], [1,2]]
    print(f"输入: {intervals2}")
    print(f"需要删除的区间数: {erase_overlap_intervals(intervals2)}")
    print(f"最优方案: {find_max_intervals(intervals2)}")

复杂度分析

• 时间复杂度：O(n log n)

  • 主要开销在排序，比较和选择过程为 O(n)

• 空间复杂度：O(1)

  • 只使用了常数额外空间（不考虑排序的空间开销）

相关LeetCode题目

1. 435. 无重叠区间

   • 经典区间调度问题

2. 452. 用最少数量的箭引爆气球

   • 变形：寻找重叠区间

3. 253. 会议室 II

   • 扩展：需要多少个会议室

算法应用

区间调度贪心算法在现实中有广泛应用：

1. 会议室预订系统

   • 在有限的会议室中安排最多的会议

2. CPU任务调度

   • 操作系统中的进程调度

3. 资源分配问题

   • 时间段资源的最优分配

总结

区间调度问题完美展示了贪心算法的核心思想：

1. 贪心选择性质：问题的整体最优解可以通过一系列局部最优选择得到
2. 最优子结构：问题的最优解包含子问题的最优解
3. 关键策略：选择结束时间最早的区间，为后续留出最多空间

通过这个经典问题，我们学会了：

• 如何分析和验证贪心策略的正确性
• 贪心算法的证明方法
• 实际应用中的算法优化

在下一篇文章中，我们将探讨另一个贪心算法的经典应用：分发糖果问题。

---

💡 思考题: 如果题目变成”选择总时长最长的不重叠区间组合”，贪心策略还适用吗？为什么？

📚 扩展阅读:

• 《算法导论》第16章 贪心算法
• 《算法设计与分析基础》第9章