1
class Solution {
2
  public int videoStitching(int[][] clips, int time) {
3
    Arrays.sort(clips, (x, y) -> x[0] == y[0] ? y[1] - x[1] : x[0] - y[0]);
4
    int n = clips.length;
5
    int interval[] = new int[2];
6
    int cuts = 0;
7
    while (true) {
8
      cuts++;
9
      int can_reach = 0;
10
      for (int i = interval[0]; i <= interval[1]; i++) {
11
        int j = 0;
12
        while (j < n) {
13
          if (clips[j][0] < i) {
14
            j++;
15
          } else if (clips[j][0] == i) {
16
            can_reach = Math.max(can_reach, clips[j][1]);
17
            j++;
18
          } else {
19
            break;
20
          }
21
        }
22
        if (can_reach >= time) return cuts;
23
      }
24
      interval[0] = interval[1] + 1;
25
      interval[1] = can_reach;
26
      if (interval[0] > interval[1]) return -1;
27
    }
28
  }
29
}