문제 설명
T초 동안 진행된 스포츠 경기를 담은 여러 개의 영상 클립이 있다고 가정해 보겠습니다. 클립들은 서로 겹칠 수도 있고 길이도 제각각입니다. 각 클립 clips[i]는 하나의 구간(interval)을 의미하며, clips[i][0] 시점에 시작해서 clips[i][1] 시점에 끝납니다.
클립은 자유롭게 잘라 세그먼트로 만들 수 있습니다. 목표는 이 클립들을 편집해 경기 전체 구간인 [0, T]를 온전히 덮을 때 필요한 최소 클립 개수를 구하는 것입니다. 어떻게 조합해도 전체 구간을 커버할 수 없다면 -1을 반환해야 합니다.
예를 들어 입력이 [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]이고 T = 10이라면 정답은 3입니다. [0,2], [8,10], [1,9] 세 개의 클립을 선택한 뒤, [1,9]를 [1,2] + [2,8] + [8,9]로 잘라내면 최종적으로 [0,2] + [2,8] + [8,10] 세그먼트가 만들어져 [0, 10] 전체 경기를 빠짐없이 덮을 수 있기 때문입니다.
풀이 접근 방법
이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 시작 시점에서 도달할 수 있는 가장 먼 끝 지점을 미리 기록해 두고, 현재 도달 범위 안에서 가능한 한 멀리 나아가는 것입니다.
알고리즘 단계
크기가
T + 1인 배열v를 만들고 모든 요소를-1로 초기화합니다.n := clips의 크기i를 0부터 n-1까지 반복합니다:clips[i][0] > T이면 해당 클립은 필요 없으므로 건너뜁니다.v[clips[i][0]] := max(v[clips[i][0]], min(clips[i][1], T))— 같은 시작 시점에서는 가장 멀리까지 도달하는 클립만 저장합니다.
curr := v[0]— 0초부터 시작 가능한지 확인합니다.v[0]이-1이면 시작 자체가 불가능하므로-1을 반환합니다.i := 1,ret := 1,next := 0으로 초기화합니다.curr < T이고i <= n인 동안 반복합니다:i <= curr인 동안next := max(next, v[i])를 수행하고i를 1씩 증가시킵니다. 즉, 현재 도달 범위 내의 모든 지점에서 뻗어나갈 수 있는 가장 먼 지점을 찾습니다.next == curr이거나next == -1이면 더 이상 확장할 수 없다는 뜻이므로-1을 반환합니다.curr := next로 갱신하고 사용한 클립 수ret을 1 증가시킵니다.
반복 종료 후
curr >= T이면ret을, 그렇지 않으면-1을 반환합니다.
C++ 구현 예제
아래 코드를 통해 풀이 과정을 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
vector <int> v(T + 1, -1);
int n = clips.size();
for(int i = 0; i < n; i++){
if(clips[i][0] > T)continue;
v[clips[i][0]] = max(v[clips[i][0]], min(clips[i][1],
T));
}
int curr = v[0];
if(v[0] == -1)return -1;
int i = 1;
int ret = 1;
int next = 0;
while(curr < T && i <= n){
while(i <= curr){
next = max(next, v[i]);
i++;
}
if(next == curr || next == -1) return -1;
curr = next;
ret++;
}
return curr >= T? ret : -1;
}
};
main(){
vector<vector<int>> v1 = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
Solution ob;
cout << (ob.videoStitching(v1, 10));
}
입력
[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]
10
출력
3
복잡도 분석
시간 복잡도: O(n + T) — 클립 배열을 한 번 순회하고(O(n)), 이후 포인터 i가 최대 T번 이동하므로 전체적으로 선형 시간 안에 해결됩니다.
공간 복잡도: O(T) — 각 시작 시점별 최대 도달 거리를 저장하는 배열 v가 필요합니다.