1024.video-stitching.md

1024. Video Stitching

Greedy

This problem is a variant of the interval covering problem, similar to 45. Jump Game II. The goal is to cover the entire time range [0, T] using the minimum number of video clips. We start from time 0 and try to extend our coverage to time T.

To achieve this, we need to keep track of the current time we have covered. We can only select intervals that overlap with the current time we have covered. Therefore, it is essential to sort the intervals by their start time. Sorting ensures that we can always select the next interval with the smallest start time, which helps in making the optimal choice at each step.

For each current time we have covered, we look for intervals that overlap with it. Among these overlapping intervals, we select the one that extends our coverage the farthest. We then move our current time to this farthest point. We repeat this process until we either cover the entire time range [0, T] or run out of intervals to select.

If at any point, the next interval does not overlap with the current time we have covered, it means we cannot cover the entire time range, and the task is impossible to complete.

X, X, X, X, X, X, X, X, X
c
|-----|
|--|
|--------|

         c
   |--|
   |-----|
      |-------|
      |------------|
      |-----|
         |------------|
                      
                      c
                

Edge cases: The next interval has no overlap with the current time we have covered.

X, X, X, X, X, X, X, X, X
c
|-----|
|--|
|--------|
  
         c     
               |------| // No overlap, we can't cover the whole time range

fun videoStitching(clips: Array<IntArray>, time: Int): Int {
    clips.sortBy { it[0] }
    
    val n = clips.size
    var count = 0
    var i = 0
    var current = 0
    while (current < time && i < n) {
        // Edge case: current < next interval, no overlap, we can't cover the whole time range
        // Or alternatively, see below
        if (current < clips[i][0]) return-1
        
        // Find the farthest time we can reach from the intervals overlapping with the current time
        var farthest = current
        while (i < n && clips[i][0] <= current) {
            farthest = maxOf(farthest, clips[i][1])
            i++
        }
        
        // Or we can check if we move or not. If we still stay at the same time, it means we can't cover the whole time range
        // if (current == farthest) return -1

        // Move to the farthest time we can reach
        current = farthest
        count++
    }
    return if (current < time) -1 else count
}