贪心

455、分发饼干

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可 以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这 个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到 没有满足条件的饼干存在。

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()
        i , j = 0, 0
        while i < len(g) and j < len(s):
            if s[j] >= g[i]:
                i += 1
                j += 1
            else:
                j += 1
        return i

135、分发糖果

做完了题目 455，你会不会认为存在比较关系的贪心策略一定需要排序或是选择？虽然这一 道题也是运用贪心策略，但我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1； 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的 糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数 不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历， 分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一 侧的大小关系。

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        if n < 2:
            return n
        res = [1]
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                res.append(res[i - 1] + 1)
            else:
                res.append(1)
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1] and res[i] <= res[i + 1]:
                res[i] = res[i + 1] + 1
        return sum(res)

435、无重叠区间

求最少的移除区间个数，等价于尽量多保留不重叠的区间。在选择要保留区间时，区间的结 尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。

因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。 具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选 择的区间不重叠的区间。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        if n == 0:
            return 0
        def sortKey(x):
            return x[1]
        intervals.sort(key=sortKey)
        res = [intervals[0]]
        prev = res[0][1]
        for i in range(1, n):
            if intervals[i][0] >= prev:
                prev = intervals[i][1]
                res.append(intervals[i])
        n2 = len(res)
        return n - n2