算法刷题记三（贪心）-蒲公英云

算法刷题记三（贪心）

文章目录

- 分发饼干（8/2-455）
- 无重叠区间（8/3-435）

分发饼干（8/2-455）

在这里插入图片描述

解析：

给一个孩子的饼干应当尽量小并且又能满足该孩子，这样大饼干才能拿来给满足度比较大的孩子。
因为满足度最小的孩子最容易得到满足，所以先满足满足度最小的孩子。

在以上的解法中，我们只在每次分配时饼干时选择一种看起来是当前最优的分配方法，但无法保证这种局部最优的分配方法最后能得到全局最优解。我们假设能得到全局最优解，并使用反证法进行证明，即假设存在一种比我们使用的贪心策略更优的最优策略。如果不存在这种最优策略，表示贪心策略就是最优策略，得到的解也就是全局最优解。

证明：假设在某次选择中，贪心策略选择给当前满足度最小的孩子分配第 m 个饼干，第 m 个饼干为可以满足该孩子的最小饼干。假设存在一种最优策略，可以给该孩子分配第 n 个饼干，并且 m < n。我们可以发现，经过这一轮分配，贪心策略分配后剩下的饼干一定有一个比最优策略来得大。因此在后续的分配中，贪心策略一定能满足更多的孩子。也就是说不存在比贪心策略更优的策略，即贪心策略就是最优策略。

在这里插入图片描述

Java实现：

class Solution { 
    public int findContentChildren(int[] g, int[] s) { 
        if (g == null || s == null) return 0;
        Arrays.sort(g);
        Arrays.sort(s);
        int gi = 0, si = 0;
        while (gi < g.length && si < s.length) { 
            if (g[gi] <= s[si]) { 
                gi++;
            }
            si++;
        }
        return gi;   
    }
}

在这里插入图片描述

无重叠区间（8/3-435）

在这里插入图片描述

解析：

在这里插入图片描述

Java实现：

class Solution { 
    public int eraseOverlapIntervals(int[][] intervals) { 
        if (intervals.length == 0) { 
            return 0;
        }
        //排序
        Arrays.sort(intervals, new Comparator<int[]>() { 
            public int compare(int[] interval1, int[] interval2) { 
                return interval1[1] - interval2[1];
            }
        });
        int n = intervals.length;  //区间的个数
        int end = intervals[0][1];  //首区间的结尾值
        int ans = 1;  //统计
        for (int i = 1; i < n; ++i) { 
            if (intervals[i][0] >= end) {  //如果当前区间的 首值 大于 首区间的 结尾值，就赋值替换
                ++ans;  
                end = intervals[i][1];
            }
        }
        return n - ans;
    }
}