1
/** https://leetcode.com/problems/video-stitching/
2
 * @param {number[][]} clips
3
 * @param {number} time
4
 * @return {number}
5
 */
6
var videoStitching = function (clips, time) {
7
  // Memo
8
  this.memo = new Map();
9

10
  // Sort the clips for easier iteration
11
  clips.sort((a, b) => a[0] - b[0]);
12

13
  // If the output is `Infinity` it means the task is impossible
14
  let out = dp(clips, time, 0, -1);
15
  return out === Infinity ? -1 : out;
16
};
17

18
var dp = function (clips, time, index, endTime) {
19
  let key = `${index}_${endTime}`;
20

21
  // Base, we got all the clip we need
22
  if (endTime >= time) {
23
    return 0;
24
  }
25

26
  // Reach end of the clip array
27
  if (index === clips.length) {
28
    return Infinity;
29
  }
30

31
  // Return form memo
32
  if (this.memo.has(key) === true) {
33
    return this.memo.get(key);
34
  }
35

36
  // There are 2 choices, include clip in current `index` or exclude
37
  // Include clip in current `index`
38
  let include = Infinity;
39

40
  // We can only include clip in current `index` if either:
41
  // - the `endTime` is -1 and current clip's starting is 0, in which this clip is the first segment
42
  // - the `endTime` is greater than current clip's starting time, in which this clip has end time greater than our `endTime`
43
  if ((endTime < 0 && clips[index][0] === 0) || endTime >= clips[index][0]) {
44
    // Update the next `endTime` with the current clip's end time, `clips[index][1]`
45
    let nextEndTime = clips[index][1];
46
    include = 1 + dp(clips, time, index + 1, nextEndTime);
47
  }
48

49
  // Exclude clip in current `index`
50
  let exclude = dp(clips, time, index + 1, endTime);
51

52
  // Find which one has less clips
53
  let count = Math.min(include, exclude);
54

55
  // Set memo
56
  this.memo.set(key, count);
57

58
  return count;
59
};