1024. Video Stitching

1024. Video Stitching

https://leetcode.com/problems/video-stitching/

문제

풀이(Recursion)

문제에서 [0, time]으로 만드는 최소 클립의 개수를 구하는 것이 목표이다.
일단 0이 앞으로 오도록 오름차순 정렬을 해야 한다.
Example 1을 예제로 한다면
clips = [[0, 2], [1, 5], [1, 9], [4, 6], [5, 9], [8, 10]]이 될 것이다.
이제 클립을 여러 세그먼트로 자를 수 있는데 이 부분이 핵심 키포인트다.
예를 들어 [[0, 2], [1, 5]]를 세그먼트로 나누어 합치려면 [1, 5] => [2, 5]로 바꿀 수 있다. 즉 자르려는 클립의 start 부분이 합치려는 클립의 start, end 사이에 있으면 하나로 합칠 수 가 있다.
[[0, 2], [1, 5]] => [0, 5]가 되고 이 클립은 [4, 6], [5, 9]와 합칠 수 있다. 그 이유는 0 < 4 <= 5, 0 < 5 <= 5이기 때문이다. 이런식으로 하여 합칠 수 있는 경우 중에서 최소값을 리턴하면 된다.

clips을 정렬했기 때문에 start = 0인 것이 여러개 있을 수 있다. 그래서 start = 0인 것들로 시작하여 최소값을 찾는다. 합칠 수 있는 조건이 되면 다음 것을 탐색하고 만약 end가 구하고자하는 time보다 크거 같으면 리턴한다.

결과(Recursion)