贪心算法是一种在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的算法策略。以下是贪心算法的主要变种、对应的模板和解决的问题特点。

1. 区间调度问题

问题特点

• 需要从一组区间中选择最大数量的不重叠区间
• 通常要求最大化区间数量或最小化冲突

Python模板

def interval_scheduling(intervals):
    """
    区间调度问题：选择最多的不重叠区间
    :param intervals: List[List[int]] 区间列表，每个区间为[start, end]
    :return: List[List[int]] 选择的不重叠区间
    """
    if not intervals:
        return []
    
    # 按结束时间排序
    intervals.sort(key=lambda x: x[1])
    
    result = []
    # 第一个区间总是被选择
    result.append(intervals[0])
    last_end = intervals[0][1]
    
    # 遍历剩余区间
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        # 如果当前区间开始时间 >= 上一个选择区间的结束时间
        if start >= last_end:
            result.append(intervals[i])
            last_end = end
    
    return result

# 使用示例
intervals = [[1, 3], [2, 4], [3, 5], [6, 7]]
selected = interval_scheduling(intervals)
print(f"最多可以选择 {len(selected)} 个不重叠区间: {selected}")

2. 区间覆盖问题

问题特点

• 用最少的区间覆盖整个目标区间
• 需要选择能够覆盖目标范围的最小区间集合

Python模板

def interval_cover(target_interval, intervals):
    """
    区间覆盖问题：用最少的区间覆盖目标区间
    :param target_interval: List[int] 目标区间 [start, end]
    :param intervals: List[List[int]] 可用区间列表
    :return: List[List[int]] 选择的区间列表
    """
    if not intervals:
        return []
    
    # 按开始时间排序
    intervals.sort(key=lambda x: x[0])
    
    result = []
    target_start, target_end = target_interval
    current_end = target_start
    i = 0
    n = len(intervals)
    
    while current_end < target_end and i < n:
        # 找到能覆盖当前起点且结束时间最远的区间
        candidate = None
        while i < n and intervals[i][0] <= current_end:
            if candidate is None or intervals[i][1] > candidate[1]:
                candidate = intervals[i]
            i += 1
        
        if candidate is None:
            return []  # 无法覆盖
        
        result.append(candidate)
        current_end = candidate[1]
    
    return result if current_end >= target_end else []

# 使用示例
target = [0, 10]
intervals = [[0, 3], [2, 6], [5, 8], [7, 10]]
selected = interval_cover(target, intervals)
print(f"覆盖区间 {target} 需要的最小区间数: {len(selected)}, 区间: {selected}")

3. 分配问题

问题特点

• 将资源分配给需求方，最大化满足需求的数量
• 常见的如饼干分配、任务分配等

Python模板

def assign_cookies(g, s):
    """
    饼干分配问题：用饼干满足尽可能多的孩子
    :param g: List[int] 孩子的胃口值
    :param s: List[int] 饼干的尺寸
    :return: int 最多能满足的孩子数量
    """
    g.sort()  # 孩子胃口排序
    s.sort()  # 饼干尺寸排序
    
    child_i = cookie_j = 0
    satisfied = 0
    
    while child_i < len(g) and cookie_j < len(s):
        if s[cookie_j] >= g[child_i]:
            # 当前饼干可以满足当前孩子
            satisfied += 1
            child_i += 1
        cookie_j += 1
    
    return satisfied

# 使用示例
children = [1, 2, 3]  # 孩子的胃口
cookies = [1, 1]      # 饼干的尺寸
result = assign_cookies(children, cookies)
print(f"最多能满足 {result} 个孩子")

4. 跳跃游戏问题

问题特点

• 判断是否能到达终点或找到到达终点的最少步数
• 每一步选择能跳到最远的位置

Python模板

def can_jump(nums):
    """
    跳跃游戏I：判断是否能到达最后一个位置
    :param nums: List[int] 每个位置的最大跳跃长度
    :return: bool 是否能到达终点
    """
    max_reach = 0
    n = len(nums)
    
    for i in range(n):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= n - 1:
            return True
    
    return False

def min_jumps(nums):
    """
    跳跃游戏II：到达最后一个位置的最少跳跃次数
    :param nums: List[int] 每个位置的最大跳跃长度
    :return: int 最少跳跃次数
    """
    if len(nums) <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    for i in range(len(nums) - 1):  # 不需要检查最后一个位置
        farthest = max(farthest, i + nums[i])
        
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            if current_end >= len(nums) - 1:
                break
    
    return jumps

# 使用示例
nums1 = [2, 3, 1, 1, 4]
print(f"是否能跳到终点: {can_jump(nums1)}")
print(f"最少跳跃次数: {min_jumps(nums1)}")

nums2 = [3, 2, 1, 0, 4]
print(f"是否能跳到终点: {can_jump(nums2)}")

5. 分数背包问题

问题特点

• 物品可以分割，选择单位价值最高的物品
• 目标是最大化总价值

Python模板

def fractional_knapsack(capacity, weights, values):
    """
    分数背包问题：物品可以分割，最大化总价值
    :param capacity: int 背包容量
    :param weights: List[int] 物品重量
    :param values: List[int] 物品价值
    :return: float 最大总价值
    """
    n = len(weights)
    # 计算单位价值并排序
    items = []
    for i in range(n):
        unit_value = values[i] / weights[i]
        items.append((unit_value, weights[i], values[i]))
    
    # 按单位价值降序排序
    items.sort(key=lambda x: x[0], reverse=True)
    
    total_value = 0.0
    remaining_capacity = capacity
    
    for unit_value, weight, value in items:
        if remaining_capacity >= weight:
            # 可以拿整个物品
            total_value += value
            remaining_capacity -= weight
        else:
            # 只能拿部分物品
            total_value += unit_value * remaining_capacity
            break
    
    return total_value

# 使用示例
capacity = 50
weights = [10, 20, 30]
values = [60, 100, 120]
max_value = fractional_knapsack(capacity, weights, values)
print(f"背包能装的最大价值: {max_value}")

6. 霍夫曼编码问题

问题特点

• 构建最优前缀编码，最小化编码总长度
• 使用优先队列（最小堆）选择频率最小的两个节点

Python模板

import heapq

class Node:
    def __init__(self, char, freq, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right
    
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(chars, freqs):
    """
    构建霍夫曼树
    :param chars: List[str] 字符列表
    :param freqs: List[int] 频率列表
    :return: Node 霍夫曼树的根节点
    """
    # 创建最小堆
    heap = []
    for i in range(len(chars)):
        heapq.heappush(heap, Node(chars[i], freqs[i]))
    
    # 构建霍夫曼树
    while len(heap) > 1:
        # 取出频率最小的两个节点
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        
        # 创建新节点，频率为两个子节点频率之和
        merged = Node(None, left.freq + right.freq, left, right)
        heapq.heappush(heap, merged)
    
    return heapq.heappop(heap) if heap else None

def generate_codes(root, current_code, codes):
    """
    生成霍夫曼编码
    :param root: Node 当前节点
    :param current_code: str 当前编码
    :param codes: dict 存储编码结果
    """
    if root is None:
        return
    
    # 如果是叶子节点，存储编码
    if root.char is not None:
        codes[root.char] = current_code
        return
    
    # 递归处理左右子树
    generate_codes(root.left, current_code + "0", codes)
    generate_codes(root.right, current_code + "1", codes)

def huffman_coding(chars, freqs):
    """
    霍夫曼编码主函数
    :param chars: List[str] 字符列表
    :param freqs: List[int] 频率列表
    :return: dict 字符到编码的映射
    """
    root = build_huffman_tree(chars, freqs)
    codes = {}
    generate_codes(root, "", codes)
    return codes

# 使用示例
chars = ['a', 'b', 'c', 'd', 'e']
freqs = [5, 9, 12, 13, 16]
codes = huffman_coding(chars, freqs)
print("霍夫曼编码结果:")
for char, code in codes.items():
    print(f"{char}: {code}")

7. 活动选择问题变种

问题特点

• 需要同时考虑多个约束条件
• 可能涉及权重、资源限制等

Python模板

def weighted_interval_scheduling(intervals):
    """
    带权区间调度：每个区间有权重，选择权重和最大的不重叠区间
    :param intervals: List[Tuple] 区间列表，每个区间为(start, end, weight)
    :return: List[Tuple] 选择的区间列表
    """
    if not intervals:
        return []
    
    # 按结束时间排序
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)
    
    # 计算每个区间之前最近的不重叠区间
    prev = [-1] * n
    for i in range(n):
        for j in range(i - 1, -1, -1):
            if intervals[j][1] <= intervals[i][0]:
                prev[i] = j
                break
    
    # 动态规划计算最大权重
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        # 不选择当前区间
        dp[i] = dp[i - 1]
        # 选择当前区间
        if prev[i - 1] != -1:
            dp[i] = max(dp[i], dp[prev[i - 1] + 1] + intervals[i - 1][2])
        else:
            dp[i] = max(dp[i], intervals[i - 1][2])
    
    # 回溯找出选择的区间
    result = []
    i = n
    while i > 0:
        if dp[i] != dp[i - 1]:
            result.append(intervals[i - 1])
            i = prev[i - 1] + 1 if prev[i - 1] != -1 else 0
        else:
            i -= 1
    
    result.reverse()
    return result

# 使用示例
weighted_intervals = [(1, 3, 5), (2, 5, 6), (4, 6, 5), (6, 7, 4), (5, 8, 11), (7, 9, 2)]
selected = weighted_interval_scheduling(weighted_intervals)
total_weight = sum(interval[2] for interval in selected)
print(f"最大权重和: {total_weight}, 选择的区间: {selected}")

8. 加油站问题

问题特点

• 环形路线上的加油问题
• 需要找到能够完成环形路线的起点

Python模板

def can_complete_circuit(gas, cost):
    """
    加油站问题：判断是否能完成环形路线
    :param gas: List[int] 每个加油站的油量
    :param cost: List[int] 到下一个加油站的耗油量
    :return: int 起始加油站索引，-1表示无法完成
    """
    n = len(gas)
    total_gas = total_cost = 0
    current_gas = 0
    start_index = 0
    
    for i in range(n):
        total_gas += gas[i]
        total_cost += cost[i]
        current_gas += gas[i] - cost[i]
        
        # 如果当前油量不足，从下一个加油站重新开始
        if current_gas < 0:
            start_index = i + 1
            current_gas = 0
    
    return start_index if total_gas >= total_cost else -1

# 使用示例
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
start = can_complete_circuit(gas, cost)
print(f"可以从加油站 {start} 开始完成环形路线" if start != -1 else "无法完成环形路线")

贪心算法通用解题思路

1. 问题分析：确定问题是否具有贪心选择性质
2. 贪心策略：设计每一步的最优选择策略
3. 正确性证明：证明贪心策略能得到全局最优解
4. 实现：编写代码实现贪心策略

贪心算法的适用条件

• 贪心选择性质：每一步的局部最优选择能导致全局最优解
• 最优子结构：问题的最优解包含子问题的最优解
• 无后效性：当前的选择不会影响后续选择的结果

这些模板覆盖了贪心算法的主要变种，在实际应用中可以根据具体问题进行调整和优化。