Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1024.html
1024. Video Stitching
Level
Medium
Description
You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.
Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. We can cut these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].
Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event ([0, T]). If the task is impossible, return -1.
Example 1:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation:
We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].
Example 2:
Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation:
We can’t cover [0,5] with only [0,1] and [0,2].
Example 3:
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9
Output: 3
Explanation:
We can take clips [0,4], [4,7], and [6,9].
Example 4:
Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation: Notice you can have extra video after the event ends.
Note:
1 <= clips.length <= 1000 <= clips[i][0], clips[i][1] <= 1000 <= T <= 100
Solution
Use priority queue. Store all the clips into a priority queue, where the clips are sorted so that the clip with the smallest start time is polled first. In case of a tie, the clip with the largest end time is polled first. The reason is that if two clips have the same start time, using the clip with a larger end time is always optimal.
Initially, the total end time is 0. While the priority queue is not empty and the total end time is less than T, poll one clip from the priority queue. If the clip’s start time is greater than the total end time, then the task is impossible, so return -1. Otherwise, if the clip’s end time is greater than the total end time, then the clip is needed, so update the total end time and increase the number of clips needed by 1. After updating the total end time, for each clip in the priority queue, if the clip’s start time is less than the total end time, update the clip’s start time using the total end time, and if the clip’s start time becomes greater or equal to the clip’s end time after updating, remove it from the priority queue since it will not be needed.
Finally, if the total end time is greater than or equal to T, return the number of clips needed. Otherwise, the task is impossible, so return -1.
-
class Solution { public int videoStitching(int[][] clips, int T) { PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() { public int compare(int[] clip1, int[] clip2) { if (clip1[0] != clip2[0]) return clip1[0] - clip2[0]; else return clip2[1] - clip1[1]; } }); for (int[] clip : clips) priorityQueue.offer(clip); int count = 0; int curEnd = 0; while (!priorityQueue.isEmpty() && curEnd < T) { int[] clip = priorityQueue.poll(); int start = clip[0], end = clip[1]; if (start > curEnd) return -1; if (end > curEnd) { curEnd = end; count++; } while (!priorityQueue.isEmpty() && priorityQueue.peek()[0] < curEnd) { int[] nextClip = priorityQueue.poll(); nextClip[0] = curEnd; if (nextClip[0] < nextClip[1]) priorityQueue.offer(nextClip); } } return curEnd >= T ? count : -1; } } -
class Solution: def videoStitching(self, clips: List[List[int]], time: int) -> int: last = [0] * time for a, b in clips: if a < time: last[a] = max(last[a], b) ans = mx = pre = 0 for i, v in enumerate(last): mx = max(mx, v) if mx <= i: return -1 if pre == i: ans += 1 pre = mx return ans ############ class Solution(object): def videoStitching(self, clips, T): """ :type clips: List[List[int]] :type T: int :rtype: int """ count = collections.defaultdict(list) for cl in clips: if cl[0] in count: if cl[1] - cl[0] > count[cl[0]][1] - count[cl[0]][0]: count[cl[0]].pop() count[cl[0]] = cl else: count[cl[0]] = cl if 0 not in count: return -1 prev = 0 cur = count[0][1] next = cur res = 1 while cur < T: hasFind = False for c in range(cur, prev, -1): if c in count: if count[c][1] > next: next = count[c][1] prev = c hasFind = True if not hasFind: return -1 cur = next res += 1 return res -
class Solution { public: int videoStitching(vector<vector<int>>& clips, int time) { vector<int> last(time); for (auto& v : clips) { int a = v[0], b = v[1]; if (a < time) { last[a] = max(last[a], b); } } int mx = 0, ans = 0; int pre = 0; for (int i = 0; i < time; ++i) { mx = max(mx, last[i]); if (mx <= i) { return -1; } if (pre == i) { ++ans; pre = mx; } } return ans; } }; -
func videoStitching(clips [][]int, time int) int { last := make([]int, time) for _, v := range clips { a, b := v[0], v[1] if a < time { last[a] = max(last[a], b) } } ans, mx, pre := 0, 0, 0 for i, v := range last { mx = max(mx, v) if mx <= i { return -1 } if pre == i { ans++ pre = mx } } return ans } func max(a, b int) int { if a > b { return a } return b }