[LeetCode] 1024. Video Stitching

1. 문제 출처: https://leetcode.com/problems/video-stitching/

Video Stitching - LeetCode

문제

time초 동안 진행된 스포츠 이벤트의 비디오 클립이 주어집니다. 비디오 클립들은 각각 길이가 다르며, 서로 중첩될 수 있습니다.

 

각 비디오 클립은 clips 배열에 clips[i] = [start_i, end_i] 형태로 주어지며, start_i는 클립의 시작 시간을 end_i는 클립의 종료 시간을 가르킵니다.

 

이 클립들을 더 작은 크기의 세그먼트 클립으로 자유롭게 자를 수 있는데,

• 예를들어, [0 ,7]의 클립은 [0, 1] + [1, 3] + [3, 7]의 세그먼트로 자를 수 있습니다.

 

전체 이벤트 시간 [0, time]을 커버하는 세그먼트로 자를 수 있는 최소 클립의 수 를 반환하라. 만약 불가능하다면, -1을 반환하라.

예제

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 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].

Input: clips = [[0,1],[1,2]], time = 5
Output: -1

Explanation: We can't cover [0,5] with only [0,1] and [1,2].

풀이

클립을 자를 수 있다는 말에 문제가 복잡하게 생각될 수 있는데, 결국 구해야 하는 결과는 [0, time]을 커버하는 하는 클립의 조합 중, 가장 작은 클립의 수를 찾으라는 것으로 볼 수 있다.

 

문제를 풀기 위해 Greedy 방법으로 접근하였다.

 

다음 그림을 살펴보자.

 

위의 그림은 클립 별로 색을 달리하여 타임라인 위에 그린 그림이다. 이 그림에서 전체 타임라인을 커버할 수 있도록 클립을 선택해보자.

 

1차적으로 파란색([0, a]) 클립은 어떤 선택의 여지도 없이 선택되어야 한다. [0, b]시간대를 커버하는 유일한 클립이기 때문이다.

 

파란색 클립을 선택하고 나면 2가지(빨강, 초록) 클립의 선택 사항이 존재하는데, 보라색의 경우는 [a, d] 시간대를 커버하지 못하므로 파란색 다음으로 선택되기에는 어려움이 있기 때문이다. 그렇다면, 빨강과 초록 중 어떤 클립을 선택하는 것이 이득일까. 초록 클립을 선택하는 것이 더 이득이 될 것이다. 이유는 초록 클립이 파란 클립이 커버하지 못하는 영역을 빨간 클립보다 더 많이 커버하기 때문이다.

 

마지막으로는 초록 클립이 커버하지 못하는 나머지 영역을 커버하는 보라색이 선택되어야 한다.

 

이와 같은 일련의 과정을 순차적으로 정리하면 다음과 같다.

 

1. clips을 클립의 시작시간 순서로 정렬
2. 현재까지 커버된 시간을 표시할 coverd_time을 선언 및 초기화: corvered_time = 0;
3. 다음에 선택할 후보 클립이 커버하는 시간을 표시할 candi_time을 선언 및 초기화: candi_time = 0;
4. clips를 순회하면서 다음의 과정 수행
   • 만약, 클립의 시작시간 > corvered_time 이라면, candi_time을 만드는 클립을 선택: corvered_time = candi_time; count += 1;
   • 위 과정 이후
     • 클립의 시작시간 > corvered_time: return -1;
     • 클립의 종료시간 > candi_time: candi_time = clip's end;
     • clip's end >= time: return count + 1;

var videoStitching = function(clips, time) {
    clips.sort((a, b) => a[0] - b[0]);

    let ans = 0;
    let covered_time = 0;
    let tmp = [0, 0];
    for (let [start, end] of clips) {
        if (start > curr[1]) {
            curr = tmp.slice();
            ans += 1;
        }

        if (start > curr[1]) { return -1; }

        if (end > tmp[1]) {
            tmp = [start, end];
            if (end >= time) { return ans += 1;}
        }
    }
    return -1;
};

Github: 1024.js

opwe37/Algorithm-Study