Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1024. Video Stitching

Time: $O(n\log n)$

Space: $O(1)$

			


class Solution {
 public:
  int videoStitching(vector<vector<int>>& clips, int time) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    sort(std::begin(clips), std::end(clips));

    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;
  }
};




			


class Solution {
  public int videoStitching(int[][] clips, int time) {
    int ans = 0;
    int end = 0;
    int farthest = 0;

    Arrays.sort(clips, (a, b) -> 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;
  }
}




			


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