区间覆盖问题 题目描述 给定一个目标区间 [start, end] 和一组小区间 intervals ，判断这些小区间是否能完全覆盖目标区间。如果可以，请找出所需的最少小区间数量；如果不能，则返回无法覆盖。例如，目标区间为 [0, 5] ，小区间为 [[0, 2], [1, 3], [3, 5]] ，则答案是 2 （选择 [0, 2] 和 [3, 5] 或 [1, 3] 和 [3, 5] ）。 解题过程 步骤 1: 问题分析 目标 ：用最少的区间覆盖 [start, end] 。 关键点 ： 覆盖必须连续，不能有间隙。 小区间可能重叠或分散。 思路 ：贪心算法。每次选择能覆盖当前起点且延伸最远的区间。 步骤 2: 预处理区间 将小区间按起点升序排序，起点相同则按终点降序（优先选更长的区间）。 初始化当前覆盖终点 cur_end = start ，所需区间数 count = 0 ，索引 i = 0 。 步骤 3: 贪心选择 在 cur_end < end 时循环： 选择所有起点 ≤ cur_end 的区间中，终点最大的区间（即延伸最远）。 如果无法找到（即所有起点都 > cur_end ），说明出现间隙，覆盖失败。 将 cur_end 更新为选中区间的终点， count++ 。 若最终 cur_end >= end ，返回 count ；否则返回失败。 步骤 4: 示例演练 目标区间： [0, 5] ，小区间： [[0, 2], [1, 3], [3, 5]] 。 排序后： [[0, 2], [1, 3], [3, 5]] 。 初始 cur_end = 0 ， count = 0 。 第一轮：起点 ≤ 0 的区间有 [0,2] 和 [1,3] ，最大终点为 3 ，选 [1,3] ， cur_end = 3 ， count = 1 。 第二轮：起点 ≤ 3 的区间有 [3,5] ，最大终点为 5 ， cur_end = 5 ， count = 2 。 覆盖完成，返回 2 。 步骤 5: 边界情况 小区间覆盖目标区间起点：若无起点 ≤ start 的区间，直接失败。 区间重叠：贪心总能选到延伸最远的区间。 终点相等：排序后优先选长的区间。 总结 贪心策略通过排序和最大化延伸终点，确保每次选择最优区间，时间复杂度为 O(n log n)（排序主导）。