贪心算法是动态规划算法的一个子集，可以更高效解决一部分更特殊的问题。
核心：每一步都做出一个局部最优的选择，最终的结果就是全局最优。

跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

  1. class Solution:
  2.     def canJump(self, nums):
  3.         # 初始化当前能到达最远的位置
  4.         max_p = 0       
  5.         # i为当前位置，nums[i]是当前位置的跳数
  6.         for i in range(len(nums)):
  7.             # 如果当前位置能到达，并且当前位置+跳数>最远位置  
  8.             if max_p >= i and max_p < i+nums[i]:
  9.                 # 更新最远能到达位置
  10.                 max_p = i+nums[i]  
  11.         return max_p >= i

分糖问题

一群小朋友排排坐，根据小朋友的得分给他们分糖果，要求满足公平原则（如果某个小朋友的得分比其邻座（左或右）得分高，则应得到更多块糖果）且每个小朋友至少得到一个糖果，设置一个方案使用到的糖果最少？
输入：[1,0,2]输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

  1. class Solution:
  2.     def candy(self, ratings):
  3.         if len(ratings) == 0:
  4.             return 0
  6.         # 每人先发一块
  7.         num = [1] * len(ratings)
  9.         # 从左开始遍历，如果高就加一
  10.         for i in range(0, len(ratings)-1):
  11.             if ratings[i+1] > ratings[i]:
  12.                 num[i+1] = num[i] + 1
  14.         # 从右开始遍历，如果高就加一
  15.         for i in range(len(ratings)-1, 0, -1):
  16.             if ratings[i] < ratings[i-1]:
  17.                 num[i-1] = max(num[i]+1, num[i-1])
  18.         return sum(num)

首先初始化每个人分配的糖果数量都是1，然后第一遍从左往右遍历，如果当前孩子的分数大于前一个孩子的分数，则当前孩子得到的糖果在前一个孩子的基础上加1；第二遍从右往左遍历，如果当前孩子的分数大于他右边孩子的分数，并且他的糖果不比他右边孩子多，则糖果数在他基础上加1；最后，将所有孩子的糖果数相加即可。
第二次遍历是为了处理数组中降序和有出现相邻孩子分数相同的情况。

合并区间

给出一个区间的集合，请合并所有重叠的区间。
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]

  1. class Solution(object):
  2.     def merge(self, intervals):
  3.         if not intervals:
  4.             return []
  5.         intervals.sort()
  7.         res = [intervals[0]]
  8.         for i in range(1, len(intervals)):
  9.             if intervals[i][0] <= res[-1][-1]:
  10.                 res[-1][-1] = max(res[-1][-1], intervals[i][-1])
  11.             else:
  12.                 res.append(intervals[i])
  13.         return res

最多可以参加的会议数目*

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
请你返回你可以参加的 最大 会议数目。
输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4
输入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
输出：4
输入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
输出：7

  1. class Solution(object):
  2.     def maxEvents(self, events):
  3.         # 核心思想就是把每个开始时间不大于当前时间(i)的结束时间放到堆中，然后判断结束时间是不是大于当前，不是直接扔掉，是就扔掉答案的同时记录一次答案
  4.         events.sort() # 排序的作用是从后往前判断开始时间，并弹出它
  5.         heap = [] # 优先队列，也可以说是小顶堆
  6.         res = 0
  7.         for i in range(1, 100001):  # 直接用数据范围（当然也可以取events结束时间的最大值，还要再写循环不够简练）
  9.             while events and events[0][0] == i: # 排序的作用
  10.                 heapq.heappush(heap, events.pop(0)[-1]) # 弹出
  12.             while heap:
  13.                 cur = heapq.heappop(heap)
  14.                 if cur >= i:
  15.                     res += 1 # 一天只能参加一次
  16.                     break
  17.             if not events and not heap:
  18.                 break # 既没有新源，也没有旧源，直接结束
  19.         return res