问题描述：【Greedy】435. Non-overlapping Intervals
解题思路：
这道题是给一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
实际上，这道题和 贪心算法之活动安排问题 很类似，贪心策略应该是每次选取结束时间最早的活动。直观上也很好理解，按这种方法选择相容活动为没有安排的活动留下尽可能多的时间。这也是把各项活动按照结束时间单调递增排序的原因。
到这道题中，我们求的是“不相容的活动”的数量。还是同样的做法，先按照右区间从小到大排序，然后遍历数组，找到重叠的区域（不相容的活动），将结果加 1；如果相容，指针向后移动。
Python3 实现：
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
N = len(intervals)
ans = 0
intervals.sort(key=lambda x: x[1]) # 按照结束时间升序
i, j = 0, 1
while i < N and j < N:
if intervals[j][0] < intervals[i][1]: # 有重叠，要删除一个
ans += 1
else: # 不重叠
i = j
j += 1
return ans
print(Solution().eraseOverlapIntervals([[1,100],[11,22],[1,11],[2,12]])) # 2
问题描述：【Greedy】452. Minimum Number of Arrows to Burst Balloons
解题思路：
这道题实际上是给一个气球区间的集合，求用最少数量的箭引爆所有气球。
我们的目的是用最少的箭来引爆所有气球，因此我们要尽量保证一支箭能穿过足够多的气球区间。其实，这道题和上面的 Leetcode 435 很类似，也属于活动时间安排问题。
因此，我们先按照右区间进行升序排列，遍历区间的过程中，左区间如果小于前面区间的右区间，说明两者有重叠；否则，说明需要增加一支箭来满足后面的区间。这种贪婪的思想可以保证尽量多的区间合并，因此能得到最少的箭数。
Python3 实现：
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
N = len(points)
if N == 0:
return 0
points.sort(key=lambda x: x[1])
ans = 1
i, j = 0, 1
while i < N and j < N:
if points[j][0] > points[i][1]: # 两者没有重叠，增加一支箭
i = j
ans += 1
j += 1
return ans
问题描述：【Math】738. Monotone Increasing Digits
解题思路：
这道题是给一个数字 N，找到小于等于 N 的单调递增数字。
这道题需要找规律，我们先全排列一下 148 看一下结果：
148 -> 148；184 -> 179；418 -> 399；481 -> 479；814 -> 799；841 -> 799
由上面可以发现规律：从左到右遍历每一位数字，找到第一个逆序对（如 481 的第一个逆序对是 (8, 1)）；然后，将逆序对的第一个位置处的数字减 1，后面补够 9；最后，答案为：逆序对前面的数字 + 逆序对位置处数字减 1 + 逆序对后面补够 9。
以 481 为例，做法如下：
- 使用两个指针 i 和 j，i 指向 4，j 指向 8；
- 因为 4 < 8，则 i 和 j 都向后移动，i 指向 8，j 指向 1；
- 因为 8 > 1，则找到第一个逆序对，8-1=7，后面补 9，最后得到答案 479。
注意：如果是 13555884 这种，结果应该为 13555799，但是按照上述规律会得到 13555879 的错误答案。因此，如果前面不是严格递增，i 不滑动（停留在第一个 8 的位置），只有 j 滑动（滑动到 4），这样我们就能定位第一个 8 的位置，从而得到正确答案。
Python3 实现：
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
S = str(N)
i, j = 0, 1
while i < len(S) and j < len(S):
if S[i] < S[j]: # 如果严格递增，i和j都向后滑动
i = j; j += 1
elif S[i] == S[j]: # 如果非严格递增，只有j向后滑动
j += 1
else: # S[i]>S[j]，即第一个逆序对位置
return int(S[:i] + str(int(S[i]) - 1) + '9' * (len(S) - i - 1))
return N
问题描述：【Math】991. Broken Calculator
解题思路：
这道题是给 X 和 Y，X 每次只能执行乘 2 或者减 1 操作，求得到 Y 所需的最少操作步数。
很明显，如果 X >= Y，那么 X - Y 就是最后的答案。对于 X < Y，刚开始想的是用广搜 BFS 求解： 从M走到N最少步数，但是由于 X 和 Y 的取值范围都为 10^9 次方，开辟一个 10^9 的空间会造成内存溢出（最大只能开 10^8 次方的空间大小）。
那么，这道题很明显不是这样求解的，具体怎么做呢？我们可以从下面的例子中观察到一些规律：
X = 3，Y = 8：3 -> 2 -> 4 -> 8；
X = 5，Y = 8：5 -> 4 -> 8；
X = 6，Y = 8：6 -> 5 -> 4 -> 8；
X = 7，Y = 8：7 -> 6 -> 5 -> 4 -> 8；
X = 7，Y = 9：7 -> 6 -> 5 -> 10 -> 9；
我们发现，可以使用逆向思维，即从 Y 到 X 去考虑。当 Y > X 时，如果 Y 为奇数，就执行加 1 操作；如果 Y 为偶数，就执行除以 2 操作。当 Y 变得比 X 小后（如 X = 7，Y = 9 中，Y 变成了 5 后，5 < X），再一步一步执行加 1 的操作，最终得到 X。
这是一种贪婪的思想，即每次考虑让 Y 先除以 2，不行的话再执行加 1 操作。时间复杂度为 O(log Y)，空间复杂度为 O(1)。
为什么这样会得到正确的答案？以下是证明，写得很清楚：坏了的计算器题解 。
Python3 实现：
class Solution:
def brokenCalc(self, X: int, Y: int) -> int:
ans = 0
while Y > X: # 从Y到X逆向思维考虑
if Y % 2 == 1: #Y为奇数+1
Y += 1
else: #Y为偶数除以2
Y //= 2
ans += 1
return ans + (X - Y) # 最后还要加上X-Y，即Y<=X后，X一步一步到达Y
