最小区间覆盖

• 描述

给定若干个子区间，至少需要选择多少个区间，能够覆盖一个大区间？

• 例题

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。
花园里总共有 n + 1 个水龙头，分别位于 [0, 1, …, n] 。
给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i - ranges[i], i + ranges[i]] 。
请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。注意：花园区域是连续的。
题目来源：Leetcode1326题
题目链接：https://leetcode-cn.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/
参考解答：
贪心算法

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        rightMost = [0] * len(ranges)
        for i, d in enumerate(ranges):
            l, r = max(0, i - d), min(n, i + d)
            rightMost[l] = max(rightMost[l], r)
        farthest, current, ans = 0, 0, 0
        for i in range(n):
            farthest = max(farthest, rightMost[i])
            if farthest == i:
                return -1
            if current == i:
                current = farthest
                ans += 1
        return ans

动态规划

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        prev = [x for x in range(n + 1)]
        for i in range(n + 1):
            l = max(i - ranges[i], 0)
            r = min(i + ranges[i], n)
            prev[r] = min(prev[r], l)
        BIG = 2**30
        dp = [0] + [BIG] * n
        for i in range(1, n + 1):
            for j in range(prev[i], i):
                if dp[j] != BIG:
                    dp[i] = min(dp[i], dp[j] + 1)
        return -1 if dp[n] == BIG else dp[n]

• 变式题
  • 视频拼接

你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
题目来源：Leetcode1024题
题目链接：https://leetcode-cn.com/problems/video-stitching
参考解答：
贪心算法

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        rightMost = list(range(T + 1))
        for i in range(len(clips)):
            l, r = min(clips[i][0], T), clips[i][1]
            rightMost[l] = max(rightMost[l], r)
        farthest, ans, current = 0, 0, 0
        for i in range(T):  # 需要注意，for循环从[0,T-1]，不能到T。
            farthest = max(farthest, rightMost[i])
            if farthest <= i:
                return -1
            if i == current:
                current = farthest
                ans += 1
        return ans

动态规划

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        dp = [T + 1] * (T + 1)
        dp[0] = 0
        for i in range(0, T+1):
            for c in clips:
                if c[0] <= i and c[1] >= i: 
                    dp[i] = min(dp[i], dp[c[0]]+1)
        return -1 if dp[T] == T + 1 else dp[T]

• 跳跃游戏II

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
题目来源：Leetcode45题
题目链接：https://leetcode-cn.com/problems/jump-game-ii
参考解答：

class Solution:
    def jump(self, nums: List[int]) -> int:
        farthest, ans, current = 0, 0, 0
        for i in range(0, len(nums) - 1):  # 注意，范围[0, len(nums)-1) 
            farthest = max(farthest, i + nums[i])
            if i == current:
                current = farthest
                ans += 1
        return ans