package leetcode;

/**
 * https://leetcode.com/problems/video-stitching/
 */
public class Problem1024 {
    public int videoStitching(int[][] clips, int T) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem1024 prob = new Problem1024();
        System.out.println(prob.videoStitching(new int[][]{
            {0, 2}, {4, 6}, {8, 10}, {1, 9}, {1, 5}, {5, 9}
        }, 10)); // 3
        System.out.println(prob.videoStitching(new int[][]{
            {0, 1}, {1, 2}
        }, 5)); // -1
        System.out.println(prob.videoStitching(new int[][]{
            {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}
        }, 9)); // 3
        System.out.println(prob.videoStitching(new int[][]{
            {0, 4}, {2, 8}
        }, 5)); // 2
    }
}

@@ -12,16 +12,42 @@
 tcode;%0A%0A
+import java.util.Arrays;%0A%0A
 /**%0A * h
@@ -189,24 +189,115 @@
     
-// TODO%0A
+Arrays.sort(clips, (a, b) -%3E %7B%0A            int cmp = a%5B0%5D - b%5B0%5D;%0A            if (cmp == 0) %7B%0A     
         
 retu
@@ -296,694 +296,968 @@
     
+   
 return 
-0;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1024 prob = new Problem1024();%0A        System.out.println(prob.videoStitching(new int%5B%5D%5B%5D%7B%0A            %7B0, 2%7D, %7B4, 6%7D, %7B8, 10%7D, %7B1, 9%7D, %7B1, 5%7D, %7B5, 9%7D%0A        %7D, 10)); // 3
+b%5B1%5D - a%5B1%5D;%0A            %7D%0A            return cmp;%0A        %7D);%0A        if (clips%5B0%5D%5B0%5D != 0) %7B%0A            return -1;%0A        %7D%0A        Integer%5B%5D memo = new Integer%5Bclips.length%5D;%0A        int n = videoStitching(clips, T, 0, memo);%0A        return n == Integer.MAX_VALUE ? -1 : n + 1;
 %0A    
+%7D%0A%0A
     
-System.out.println(prob.videoStitching(new int%5B%5D%5B%5D%7B%0A            %7B0, 1%7D, %7B1, 2%7D%0A        %7D, 5)); // -1%0A        System.out.println(prob.videoStitching(new int%5B%5D%5B%5D%7B%0A            %7B0, 1%7D, %7B6, 8%7D, %7B0, 2%7D, %7B5, 6%7D, %7B0, 4%7D, %7B0, 3%7D, %7B6, 7%7D, %7B1, 3%7D, %7B4, 7%7D, %7B1, 4%7D, %7B2, 5%7D, %7B2, 6%7D, %7B3, 4%7D, %7B4, 5%7D, %7B5, 7%7D, %7B6, 9%7D%0A        %7D, 9)); // 3%0A        System.out.println(prob.videoStitching(new int%5B%5D%5B%5D%7B%0A            %7B0, 4%7D, %7B2, 8%7D%0A        %7D, 5)); // 2
+private static int videoStitching(int%5B%5D%5B%5D clips, int t, int idx, Integer%5B%5D memo) %7B%0A        if (idx == clips.length %7C%7C clips%5Bidx%5D%5B1%5D %3E= t) %7B%0A            return 0;%0A        %7D%0A        if (memo%5Bidx%5D != null) %7B%0A            return memo%5Bidx%5D;%0A        %7D%0A        int min = Integer.MAX_VALUE;%0A        for (int i = idx + 1; i %3C clips.length; i++) %7B%0A            if (clips%5Bidx%5D%5B0%5D %3C= clips%5Bi%5D%5B0%5D && clips%5Bi%5D%5B0%5D %3C= clips%5Bidx%5D%5B1%5D) %7B%0A                int n = videoStitching(clips, t, i, memo);%0A                if (n != Integer.MAX_VALUE) %7B%0A                    min = Math.min(min, n + 1);%0A                %7D%0A            %7D%0A        %7D%0A        memo%5Bidx%5D = min;%0A        return min;
 %0A   

Solve problem 1024