区间调度之最多不相交区间问题 题目描述 给定一组区间 intervals ，每个区间由起始点 start 和结束点 end 表示。要求选择尽可能多的区间，使得这些区间之间互不重叠（即任意两个区间都没有交集）。最终返回可以选择的 最大区间数量 。 示例 输入： intervals = [[1,3], [2,4], [3,6]] 输出： 2 解释：最多可以选择两个不重叠的区间，例如 [1,3] 和 [3,6] （注意端点相接不算重叠，但实际题目中需根据题意判断是否允许端点重叠，本题通常按不允许重叠处理，即结束时间需严格小于下一个区间的开始时间）。 解题过程 步骤1：理解问题本质 此问题属于 贪心算法 的经典应用。关键点在于：如何贪心地选择区间，使得剩余空间尽可能容纳更多区间。直接尝试所有组合会因指数级复杂度不可行。 步骤2：贪心策略的直觉 优先选择 结束时间最早 的区间，这样能为后续区间留下更多可用时间。 反证 ：如果选择结束晚的区间，可能占用较长时间，导致挤掉多个早结束的区间。 步骤3：算法步骤 排序 ：将区间按照结束时间 end 从小到大排序。 遍历选择 ： 初始化已选区间计数 count = 1 （至少可选第一个区间），记录当前已选区间的结束时间 current_end 。 从第二个区间开始遍历： 如果当前区间的开始时间 start 大于等于 current_end （即不重叠），则选择该区间，更新 current_end 为当前区间的结束时间，并增加计数。 否则跳过该区间。 返回计数 count 。 步骤4：示例推演 输入： [[1,3], [2,4], [3,6]] 按结束时间排序： [[1,3], [2,4], [3,6]] （结束时间已有序）。 选择 [1,3] ， current_end = 3 ， count = 1 。 检查 [2,4] ：开始时间 2 < 3 （重叠），跳过。 检查 [3,6] ：开始时间 3 >= 3 （允许端点相接？通常题目明确要求不重叠时需 start > current_end ，但常见变体允许相接。此处按相接允许处理），选择该区间，更新 current_end = 6 ， count = 2 。 结果： 2 。 步骤5：边界情况处理 空区间列表：直接返回 0 。 区间重叠定义：需根据题目确认是否允许端点相接。若严格不重叠，判断条件应为 start > current_end 。 时间效率：排序 O(n log n) ，遍历 O(n) ，总复杂度 O(n log n) 。 步骤6：为什么贪心正确？ 结束时间最早的选择保证了剩余时间的最大化。 可形式化证明：假设存在最优解，其第一个区间不是结束最早的，总可以替换为结束最早的区间而不减少选择数量。