|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +You are given a series of video clips from a sporting event that lasted T |
| 4 | +seconds. These video clips can be overlapping with each other and have varied |
| 5 | +lengths. |
| 6 | +
|
| 7 | +Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends |
| 8 | +at time clips[i][1]. We can cut these clips into segments freely: for example, |
| 9 | +a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7]. |
| 10 | +
|
| 11 | +Return the minimum number of clips needed so that we can cut the clips into |
| 12 | +segments that cover the entire sporting event ([0, T]). If the task is |
| 13 | +impossible, return -1. |
| 14 | +
|
| 15 | +Example 1: |
| 16 | +Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 |
| 17 | +Output: 3 |
| 18 | +Explanation: |
| 19 | +We take the clips [0,2], [8,10], [1,9]; a total of 3 clips. |
| 20 | +Then, we can reconstruct the sporting event as follows: |
| 21 | +We cut [1,9] into segments [1,2] + [2,8] + [8,9]. |
| 22 | +Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10]. |
| 23 | +Example 2: |
| 24 | +
|
| 25 | +Input: clips = [[0,1],[1,2]], T = 5 |
| 26 | +Output: -1 |
| 27 | +Explanation: |
| 28 | +We can't cover [0,5] with only [0,1] and [0,2]. |
| 29 | +Example 3: |
| 30 | +
|
| 31 | +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 |
| 32 | +Output: 3 |
| 33 | +Explanation: |
| 34 | +We can take clips [0,4], [4,7], and [6,9]. |
| 35 | +Example 4: |
| 36 | +
|
| 37 | +Input: clips = [[0,4],[2,8]], T = 5 |
| 38 | +Output: 2 |
| 39 | +Explanation: |
| 40 | +Notice you can have extra video after the event ends. |
| 41 | +
|
| 42 | +Note: |
| 43 | +1 <= clips.length <= 100 |
| 44 | +0 <= clips[i][0], clips[i][1] <= 100 |
| 45 | +0 <= T <= 100 |
| 46 | +""" |
| 47 | +fromtypingimportList |
| 48 | + |
| 49 | + |
| 50 | +classSolution: |
| 51 | +defvideoStitching(self,clips:List[List[int]],T:int)->int: |
| 52 | +""" |
| 53 | + Greedy is correct. The larger the coverage, the better |
| 54 | + """ |
| 55 | +clips.sort() |
| 56 | +prev_e=0 |
| 57 | +ret=0 |
| 58 | + |
| 59 | +i=0 |
| 60 | +whilei<len(clips): |
| 61 | +ifclips[i][0]>prev_e:# gap |
| 62 | +break |
| 63 | + |
| 64 | +max_e=-float("inf") |
| 65 | +whilei<len(clips)andclips[i][0]<=prev_e: |
| 66 | +max_e=max(max_e,clips[i][1]) |
| 67 | +i+=1 |
| 68 | + |
| 69 | +prev_e=max_e# take |
| 70 | +ret+=1 |
| 71 | +ifprev_e>=T: |
| 72 | +break |
| 73 | + |
| 74 | +returnretifprev_e>=Telse-1 |
| 75 | + |
| 76 | +defvideoStitching_error(self,clips:List[List[int]],T:int)->int: |
| 77 | +""" |
| 78 | + gready take the max coverage? |
| 79 | + """ |
| 80 | +A= [(s,-e,s,e)fors,einclips] |
| 81 | +A.sort() |
| 82 | +ret=1 |
| 83 | +_,_,prev_s,prev_e=A[0] |
| 84 | +ifprev_s>0: |
| 85 | +returnFalse |
| 86 | + |
| 87 | +for_,_,s,einA[1:]: |
| 88 | +ifs<=prev_eande>prev_e: |
| 89 | +prev_e=e |
| 90 | +ret+=1 |
| 91 | + |
| 92 | + |
| 93 | +if__name__=="__main__": |
| 94 | +assertSolution().videoStitching([[0,4],[2,8]],5)==2 |