当然，使用贪心算法所得到的最终解并不一定就是全局最优解。但是对许多问题来说，确实可以通过局部最优解而得到整体最优解或者是整体最优解的近似解。

一般来说，这些能够使用贪心算法解决的问题必须满足下面的两个特征：「贪⼼选择性质」和「最优子结构」。

「贪心选择」：指的是一个问题的全局最优解可以通过一系列局部最优解（贪心选择）来得到。

「最优子结构」：指的是一个问题的最优解包含其子问题的最优解。

问题的最优子结构性质是该问题能否用贪心算法求解的关键。举个例子，如下图所示，原问题 $S = \lbrace a_1, a_2, a_3, a_4 \rbrace$，在 $a_1$ 步我们通过贪心选择选出一个当前最优解之后，问题就转换为求解子问题 $S_{子问题} = \lbrace a_2, a_3, a_4 \rbrace$。如果原问题 $S$ 的最优解可以由「第 $a_1$ 步通过贪心选择的局部最优解」和「 $S_{子问题}$ 的最优解」构成，则说明该问题满足最优子结构性质。

贪心算法最难的部分不在于问题的求解，而在于是正确性的证明。常用的证明方法有「数学归纳法」和「交换论证法」。

- **数学归纳法**：先计算出边界情况（例如 $n = 1$）的最优解，然后再证明对于每个 $n$，$F_{n + 1}$ 都可以由 $F_n$ 推导出。

- **交换论证法**：从最优解出发，在保证全局最优不变的前提下，如果交换方案中任意两个元素 / 相邻的两个元素后，答案不会变得更好，则可以推定目前的解是最优解。

输入 g = [1,2,3], s = [1,1]

输出 1

解释 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1, 2, 3。虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以应该输出 1。

输入 intervals = [[1,2],[2,3],[3,4],[1,3]]

输出 1

解释 移除 [1,3] 后，剩下的区间没有重叠。

这道题我们可以转换一下思路。原题要求保证移除区间最少，使得剩下的区间互不重叠。换个角度就是：「如何使得剩下互补重叠区间的数目最多」。那么答案就变为了：「总区间个数 - 不重叠区间的最多个数」。我们的问题也变成了求所有区间中不重叠区间的最多个数。