贪心算法经典题目：合并区间、单调递增数字与监控二叉树

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

• 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
• 输出：[[1,6],[8,10],[15,18]]
• 解释：区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。

示例 2:

• 输入：intervals = [[1,4],[4,5]]
• 输出：[[1,5]]
• 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路是排序，让相邻区间尽可能重叠。按左边界或右边界排序均可，处理逻辑稍有不同。

按左边界从小到大排序后，如果 intervals[i][0] <= intervals[i - 1][1]，即当前区间左边界小于等于前一个区间右边界，则一定有重叠。

class Solution:
    def merge(self, intervals):
        result = []
        if len(intervals) == 0:
            return result
        # 按照区间的左边界进行排序
        intervals.sort(key=lambda x: x[0])
        # 第一个区间可以直接放入结果集中
        result.append(intervals[0])
        for i in range(1, len(intervals)):
            if result[-1][1] >= intervals[i][0]:
                # 发现重叠区间
                # 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的
                result[-1][1] = max(result[-1][1], intervals[i][1])
            else:
                result.append(intervals[i])
        return result

738. 单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。