【LeetCode 1024】视频拼接 Video Stitching

今天药忘吃喽~ 2021-09-22 23:38 280阅读 0赞

题目：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]  
题意为：用一个`chips[][]`数组来记录一些视频片段，`chips[i][0]`记录开始时间，`chips[i][1]`记录结束时间，给定一个最终要到达的时间点，求判断给定的视频片断，能否拼凑到要求的时间点，如果能到达，问最少需要多少个视频片段可以完成。  
举例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]  
举例部分，例如第三个例子，里面的视频碎片中，选取\[0,4\]、\[4,7\]、\[6,9\]这三个片段，刚好可以到达时间点 9，因此需要的最少的碎片数为3。  
这种题目，求最少需要多少，很容易想到贪心或者是动态规划，但明显这题目用贪心的当前最优的思想，没有办法达到最终的全局最优，因此选用动态规划的思路，那对于动态规划，主要就有两个问题：

*  定义状态量
 *  状态转移方程

这题状态量也好确定，它要求最少的碎片数，我们可以用 `dp[]`来记录到达每个时间点时需要的最少碎片数，则我们可以在`dp[T + 1]`的地方找到题目的答案。  
第二个问题是状态转移方程，我们可以将碎片分为两类，第一类是从 0开始的碎片，对于这些碎片范围内的时间点，都有`dp[i] = 1`即一个碎片就可以到达，对于第二类碎片，即不是从 0开始的，例如`[6,9]`，我们需要更新`dp[6]`到`dp[9]`的值，当前到达 6到 9之间的最少碎片数，为：`Math.min(dp[i], dp[start] + 1)`，我们这里要注意，有一些并不能完整的拼接到我们要的时间点，可能有\[0,4\]，\[5,6\]，这种是不行的。我采取的方法是：在一开始根据他们的起点进行排序，当遍历到新的一个起点非0的点i时，如果`dp[i] == 0`，即在此之前所有的视频段都不能覆盖到第 i个时间点，则这些碎片不能成段，直接返回 -1。

代码：

public int videoStitching(int[][] clips, int T) { 
            // 状态量，用于记录到达对应时间点所需的最少碎片数
            int[] dp = new int[T + 1];
            // 根据视频碎片的起点来排序
            Arrays.sort(clips, new Comparator<int[]>() { 
                @Override
                public int compare(int[] o1, int[] o2) { 
                    return o1[0] - o2[0];
                }
            });
            // 遍历所有视频碎片
            for (int[] k : clips
                 ) { 
                // 当视频碎片不在我们要的时间范围内时，直接跳过
                if (k[0] >= dp.length) continue;
                // 视频碎片没有办法连续，直接跳出返回 -1
                if (k[0] != 0 && dp[k[0]] == 0) return -1;
                // 当视频碎片的末端超过我们要求的时间，进行裁剪
                if (k[1] >= dp.length) k[1] = dp.length - 1;
                // 将视频碎片分为两类
                if (k[0] == 0) { 
                    // 从 0开始的，直接范围内的时间都置为 1个碎片可达
                    for (int i = k[0]; i <= k[1]; i++) { 
                        dp[i] = 1;
                    }
                } else { 
                    // 其他碎片段，判断新的碎片能否带来更少的所需碎片
                    int temp = dp[k[0]] + 1;
                    for (int i = k[0]; i <= k[1]; i++) { 
                        if (dp[i] == 0 || dp[i] > temp) { 
                            dp[i] = temp;
                        }
                    }
                }
            }
            // dp[T]为 0意味着未能到达 T点，因此未能拼接成功
            return dp[T] == 0? -1: dp[T];
        }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]

[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/c8301404f44e474f88c8b53c4dc54f74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]: /images/20210920/1766d7f29a9f482ab4fd11775c1f2ded.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]: /images/20210920/4cf32510b2be4957947060875d58062f.png
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html