1
class Solution {
2
 public:
3
  static bool comp(vector<int> a, vector<int> b) {
4
    if (a[0] < b[0])
5
      return true;
6
    else if (a[0] == b[0])
7
      return a[1] > b[1];
8
    return false;
9
  }
10

11
  int videoStitching(vector<vector<int>> &clips, int time) {
12
    sort(clips.begin(), clips.end(), comp);
13
    vector<vector<int>> res;
14
    // check if 0 is present or not
15
    if (clips[0][0] != 0) return -1;
16
    res.push_back(clips[0]);
17
    // if 1. First check if the required interval is already covered or not
18
    // if 2. If the first value of the already inserted element in res is equal,
19
    // then the next value if obviously smaller interval because of custom
20
    // sorting so, we should skip it if 3. Cover every value by checking if the
21
    // interval is required or not (already present?) if required then insert it
22
    // if 3.1. Check if the interval to be inserted covers the interval at the
23
    // back for example [0,4], [2,6], now if we were to insert the interval [4,
24
    // 7], then [2,6] is no more requried, then pop_back.
25
    for (int i = 1; i < clips.size(); i++) {
26
      if (res.back()[1] >= time) break;
27
      if (clips[i][0] == res.back()[0]) continue;
28
      if (clips[i][1] > res.back()[1]) {
29
        if (res.size() > 1 and res[res.size() - 2][1] >= clips[i][0]) res.pop_back();
30
        res.push_back(clips[i]);
31
      }
32
    }
33
    // Check if the compelete range from 0 to time is covered or not
34
    int prev = res[0][1];
35
    for (int i = 1; i < res.size(); i++) {
36
      if (res[i][0] > prev) return -1;
37
      prev = res[i][1];
38
    }
39
    // check explicitly for the last value
40
    if (res.back()[1] < time) return -1;
41
    return res.size();
42
  }
43
};