区间覆盖

📌 核心概念

区间覆盖问题：用最少的区间覆盖给定范围，或找到覆盖所有点的最少区间数。

贪心策略：在满足覆盖要求的前提下，每次选择能延伸最远的区间。

💻 算法实现

🎯 经典应用

💡 解题技巧

2. 跳跃问题转化

跳跃游戏本质是区间覆盖：

• 位置i能跳到的范围是[i, i+nums[i]]
• 问题转化为用最少区间覆盖[0, n-1]

📊 复杂度分析

问题	时间复杂度	空间复杂度	关键点
跳跃游戏II	O(n)	O(1)	贪心边界
视频拼接	O(n log n)	O(1)	排序+贪心
区间覆盖	O(n log n)	O(1)	排序+双指针
加油站	O(n)	O(1)	累积和
移掉K位数字	O(n)	O(n)	单调栈
连续子序列	O(n)	O(n)	哈希表

Go 代码

// 跳跃游戏II
func jump(nums []int) int {
    n := len(nums)
    if n == 1 {
        return 0
    }
 
    jumps := 0
    currentEnd := 0
    farthest := 0
 
    for i := 0; i < n-1; i++ {
        farthest = max(farthest, i+nums[i])
 
        if i == currentEnd {
            jumps++
            currentEnd = farthest
 
            if currentEnd >= n-1 {
                break
            }
        }
    }
 
    return jumps
}
 
// 视频拼接
func videoStitching(clips [][]int, time int) int {
    sort.Slice(clips, func(i, j int) bool {
        return clips[i][0] < clips[j][0]
    })
 
    count := 0
    currentEnd := 0
    nextEnd := 0
    i := 0
 
    for currentEnd < time {
        for i < len(clips) && clips[i][0] <= currentEnd {
            nextEnd = max(nextEnd, clips[i][1])
            i++
        }
 
        if nextEnd == currentEnd {
            return -1
        }
 
        count++
        currentEnd = nextEnd
 
        if currentEnd >= time {
            return count
        }
    }
 
    return count
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

🎯 经典题目

题目	LeetCode	难度	关键点
跳跃游戏	55	中等	判断能否到达
跳跃游戏II	45	中等	最少跳跃次数
视频拼接	1024	中等	区间覆盖
加油站	134	中等	环形数组
移掉K位数字	402	中等	单调栈
分割数组为连续子序列	659	中等	贪心+哈希
最少箭引爆气球	452	中等	区间重叠

---

返回：贪心算法