算法系列之贪心法

贪心法

    贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

    也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

    贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本要素

贪心选择

    贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。

    这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。

    贪心选择是采用从顶向下、以迭代的方法做出相继选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。

    对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。

    通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。

    然后，用数学归纳法证明，通过每一步贪心选择，最终可得到问题的一个整体最优解。

最优子结构

    当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。

    运用贪心策略在每一次转化时都取得了最优解。

    问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。

    贪心算法的每一次操作都对结果产生直接影响，而动态规划则不是。

    贪心算法对每个子问题的解决方案都做出选择，不能回退；动态规划则会根据以前的选择结果对当前进行选择，有回退功能。

    动态规划主要运用于二维或三维问题，而贪心一般是一维问题。

1、区间调度问题

leetcode—题435 无重叠区间

问题

    有n项工作，每项工作分别在si开始，ti结束。对每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与，即参与工作的时间段不能有重叠(即使开始的时间和结束的时间重叠都不行)，我们要尽量的选择尽可能多的工作，求我们能做的最多的工作数目

例子8

    我们有5项工作，每项工作的开始与结束时间为T = [[1,3],[2,5],[3,7],[6,9],[8,10]]则我们能做的最多的工作数目为3（选择工作1，3，5）

思路

    选择结束最早的工作，为我们要做的第一个工作，接下来，选择第一个工作结束后才开始，并且结束最早的工作，作为下一个工作，重复的进行迭代。

• 根据 结束时间将区间进行排序。
• 初始化 first_end 为第一个工作结束时间T[0][1]。
• 初始化可调度区间的数量 num= 1。
• 遍历所有的区间：
• 如果工作的开始时间大于等于 first_end：
• 则将 first_end 设置为当前工作的 end，并将num加1
• 返回 num。

def intervalScheduling(T:List[List[int]])->int:
    if not T:
        return 0
    #按结束时间进行排序
    T.sort(key = (lambda x:x[1]))	
    #初始化工作区间为1
    num = 1	
    #初始化第一个结束点
    first_end = T[0][1]
    for start,end in T:
        if start >= first_end:
            first_end = end
            num += 1
    return num

2、重叠区间问题

leetcode—题452 用最少数量的箭引爆气球

问题

    在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以y坐标并不重要，因此只要知道开始和结束的x坐标就足够了。开始坐标总是小于结束坐标。平面内最多存在$ 10^4$ 个气球。

    一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为$ x_{start}，x_{end}$， 且满足 $ x_{start} ≤ x ≤ x_{end}$，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。

例子

    输入points = [[10,16], [2,8], [1,6], [7,12]]，输出2，对于该样例，我们可以在x = 6（射爆[2,8],[1,6]两个气球）和 x = 11（射爆另外两个气球）。

思路

• 根据 x_end将气球进行排序。
• 初始化 first_end 为第一个气球结束的坐标points[0][1]。
• 初始化箭的数量 arrows = 1。
• 遍历所有的气球：
• 如果气球的开始坐标大于 first_end：
• 则增加箭的数量。
• 将 first_end 设置为当前气球的 x_end。
• 返回 arrows。

import math
def overlappingInterval(points:List[List[int]])->int:
    if not points:
       return 0
        
    # 按照结束点排序
    points.sort(key = lambda x : x[1])
    #初始化箭的数量为1
    arrows = 1
    #初始化第一个结束点
    first_end = points[0][1]
    for x_start, x_end in points:
        #如果当前的开始点大于了结束点，加一支箭，并更新下一个结束点
        if first_end < x_start:
            arrows += 1
            first_end = x_end
    
    return arrows

• 五大基本算法之贪心算法 Greedy