区间调度问题 题目描述： 给定一组区间 [start_i, end_i] ，要求选出最多的互不重叠的区间（即任意两个区间没有重叠部分），并返回最大可选取的区间数量。例如区间 [[1,3], [2,4], [3,6]] ，最大不重叠区间数为 2（如选 [1,3] 和 [3,6] ）。 解题步骤 1. 问题分析 目标是从区间集合中选出尽可能多的区间，且它们互不重叠。关键在于如何避免重叠：如果一个区间结束得早，它后面可能容纳更多区间。 2. 贪心策略 经典解法是 按结束时间升序排序 ： 每次选择结束最早的区间，然后跳过所有与它重叠的区间，再选下一个结束最早的区间。 为什么正确？因为结束越早，留给后续区间的时间越多。 3. 算法步骤 排序 ：将区间按 end_i 从小到大排序。 初始化 ： 记录已选区间的数量 count = 1 （至少选第一个区间）。 记录当前已选区间的结束时间 current_end = 第一个区间的 end 。 遍历 ：从第二个区间开始，依次检查每个区间： 如果当前区间的 start ≥ current_end ，说明不重叠，选择该区间： count++ 更新 current_end = 当前区间的 end 否则跳过（因为重叠）。 返回 count 。 4. 举例说明 区间： [[1,3], [2,4], [3,6]] 按结束时间排序： [[1,3], [2,4], [3,6]] （结束时间已升序）。 选 [1,3] ， current_end = 3 。 下一个 [2,4] ： 2 < 3 （重叠），跳过。 下一个 [3,6] ： 3 ≥ 3 （不重叠），选择， current_end = 6 。 结果：数量为 2。 5. 复杂度 排序： O(n log n) 遍历： O(n) 总复杂度： O(n log n)