Skip to content

1024. Video Stitching 👍

  • Time: $O(n\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int videoStitching(vector<vector<int>>& clips, int time) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    ranges::sort(clips.begin(), clips.end());

    int i = 0;
    while (farthest < time) {
      while (i < clips.size() && clips[i][0] <= end)
        farthest = max(farthest, clips[i++][1]);
      if (end == farthest)
        return -1;
      ++ans;
      end = farthest;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int videoStitching(int[][] clips, int time) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    Arrays.sort(clips, (a, b) -> Integer.compare(a[0], b[0]));

    int i = 0;
    while (farthest < time) {
      while (i < clips.length && clips[i][0] <= end)
        farthest = Math.max(farthest, clips[i++][1]);
      if (end == farthest)
        return -1;
      ++ans;
      end = farthest;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def videoStitching(self, clips: list[list[int]], time: int) -> int:
    ans = 0
    end = 0
    farthest = 0

    clips.sort()

    i = 0
    while farthest < time:
      while i < len(clips) and clips[i][0] <= end:
        farthest = max(farthest, clips[i][1])
        i += 1
      if end == farthest:
        return -1
      ans += 1
      end = farthest

    return ans