算法刷题记三（贪心）

迈不过友情╰ 2022-09-02 08:12 153阅读 0赞

### 文章目录 ###

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

## 分发饼干（8/2-455） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][b8920c04e6d544d5a450bb2da0e1379b.png]

--------------------

解析：

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

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

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

![在这里插入图片描述][a20d0a9ac35a4ca7a3dd8d675510553c.gif]

--------------------

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;   
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 1]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 3]

--------------------

解析：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 4]

--------------------

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;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70]: /images/20220829/63f48c8034124505aa47648b5904f43d.png
[b8920c04e6d544d5a450bb2da0e1379b.png]: /images/20220829/4c47172c17374d79b3f7046bc00e70dd.png
[a20d0a9ac35a4ca7a3dd8d675510553c.gif]: /images/20220829/4d6145f62a26469b921a1a6c240f786f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 1]: /images/20220829/0ad3477e928348f1b80960514e449b8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 2]: /images/20220829/5b119126b5ad471c8d96858d65807bf7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 3]: /images/20220829/37646e834ae7417e88a8e04309c2ffbb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 4]: /images/20220829/e137a242c0954af2a5953759eac20070.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 5]: /images/20220829/a884403f4ecc4c379d2a7a565561054d.png