You are given a series of video clips from a sporting event that lasted time seconds. These video clips can be overlapping with each other and have varying lengths.

Each video clip is described by an array clips where clips[i] = [starti, endi] indicates that the ith clip started at starti and ended at endi.

We can cut these clips into segments freely.


	For example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].


Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event [0, time]. If the task is impossible, return -1.

&nbsp;
Example 1:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
Explanation: We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].


Example 2:

Input: clips = [[0,1],[1,2]], time = 5
Output: -1
Explanation: We cannot cover [0,5] with only [0,1] and [1,2].


Example 3:

Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9
Output: 3
Explanation: We can take clips [0,4], [4,7], and [6,9].


&nbsp;
Constraints:


	1 &lt;= clips.length &lt;= 100
	0 &lt;= starti &lt;= endi &lt;= 100
	1 &lt;= time &lt;= 100


class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        dp = [float('inf')] * (T + 1)
        dp[0] = 0
        for i in range(1, T + 1):
            for start, end in clips:
                if start <= i <= end:
                    dp[i] = min(dp[start] + 1, dp[i])
        if dp[T] == float('inf'):
            return -1
        return dp[T]
class Solution {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips , (x , y) -> x[0] == y[0] ? y[1] - x[1] : x[0] - y[0]);
        int n = clips.length;
        int interval[] = new int[2];
        int cuts = 0;
        while(true){
            cuts++;
            int can_reach = 0;
            for(int i = interval[0]; i <= interval[1]; i++){
                int j = 0;
                while(j < n){
                    if(clips[j][0] < i){
                        j++;
                    }
                    else if(clips[j][0] == i){
                        can_reach = Math.max(can_reach , clips[j][1]);
                        j++;
                    }
                    else{
                        break;
                    }
                }
                if(can_reach >= time) return cuts;
            }
            interval[0] = interval[1] + 1;
            interval[1] = can_reach;
            if(interval[0] > interval[1]) return -1;
        }
    }
}
class Solution {
public:
    static bool comp(vector<int> a, vector<int> b){
        if(a[0]<b[0]) return true;
        else if(a[0]==b[0]) return a[1]>b[1];
        return false;
    }

    int videoStitching(vector<vector<int>>& clips, int time) {
        sort(clips.begin(), clips.end(), comp);
        vector<vector<int>> res;
        //check if 0 is present or not
        if(clips[0][0] != 0) return -1;
        res.push_back(clips[0]);
        //if 1. First check if the required interval is already covered or not
        //if 2. If the first value of the already inserted element in res is equal, then the next value if obviously smaller interval because of custom sorting so, we should skip it
        //if 3. Cover every value by checking if the interval is required or not (already present?) if required then insert it
        //if 3.1. Check if the interval to be inserted covers the interval at the back for example [0,4], [2,6], now if we were to insert the interval [4, 7], then [2,6] is no more requried, then pop_back.
    for(int i=1; i<clips.size(); i++){
            if(res.back()[1]>=time) break;
            if(clips[i][0]==res.back()[0]) continue;
            if(clips[i][1]>res.back()[1]){
                if(res.size()>1 and res[res.size()-2][1]>=clips[i][0]) res.pop_back();
                res.push_back(clips[i]);
            }
        }
        //Check if the compelete range from 0 to time is covered or not
        int prev = res[0][1];
        for(int i=1; i<res.size(); i++){
            if(res[i][0]>prev) return -1;
            prev = res[i][1];
        }
        //check explicitly for the last value
        if(res.back()[1]<time) return -1;
        return res.size();
    }
};
/** https://leetcode.com/problems/video-stitching/
 * @param {number[][]} clips
 * @param {number} time
 * @return {number}
 */
var videoStitching = function(clips, time) {
  // Memo
  this.memo = new Map();
  
  // Sort the clips for easier iteration
  clips.sort((a, b) => a[0] - b[0]);
  
  // If the output is `Infinity` it means the task is impossible
  let out = dp(clips, time, 0, -1);
  return out === Infinity ? -1 : out;
};

var dp = function(clips, time, index, endTime) {
  let key = `${index}_${endTime}`;
  
  // Base, we got all the clip we need
  if (endTime >= time) {
    return 0;
  }
  
  // Reach end of the clip array
  if (index === clips.length) {
    return Infinity;
  }
  
  // Return form memo
  if (this.memo.has(key) === true) {
    return this.memo.get(key);
  }
  
  // There are 2 choices, include clip in current `index` or exclude
  // Include clip in current `index`
  let include = Infinity;
  
  // We can only include clip in current `index` if either:
  // - the `endTime` is -1 and current clip's starting is 0, in which this clip is the first segment
  // - the `endTime` is greater than current clip's starting time, in which this clip has end time greater than our `endTime`
  if ((endTime < 0 && clips[index][0] === 0) ||
      endTime >= clips[index][0]) {
    // Update the next `endTime` with the current clip's end time, `clips[index][1]`
    let nextEndTime = clips[index][1];
    include = 1 + dp(clips, time, index + 1, nextEndTime);
  }
  
  // Exclude clip in current `index`
  let exclude = dp(clips, time, index + 1, endTime);
  
  // Find which one has less clips
  let count = Math.min(include, exclude);
  
  // Set memo
  this.memo.set(key, count);
  
  return count;
};
Video Stitching