1024. Video Stitching

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.

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        sort(clips.begin(), clips.end(), [](vector<int>& v1, vector<int>& v2) {
            if(v1[0] == v2[0]) return v1[1] > v2[1];
            return v1[0] < v2[0];
        });
        if(clips[0][0] != 0) return -1;
        priority_queue<int> pq;
        int res = 1;
        int e = clips[0][1];
        for(int i = 1; i < clips.size() and e < time; i++) {
            if(clips[i][0] <= e)
                pq.push(clips[i][1]);
            else {
                if(pq.empty() or pq.top() < clips[i][0]) return -1;
                e = pq.top();
                res++;
                pq.push(clips[i][1]);
            }
        }
        if(e >= time) return res;
        if(pq.top() >= time) return res + 1;
        return -1;
    }
};