1024. Video Stitching

The greedy idea is obtained from Mudin Ibrahim. Thanks for his explanation. After watch his method, I wrote the code on my own, and AC with 0ms. Actually, this problem is similar to 45. Jump Game II, the latter gave us a sorted array, which is much easier.

class Interval{
    int start;
    int end;
    public Interval(int s, int e) {
	start = s;
	end = e;
    }
}
    
public int videoStitching(int[][] clips, int T) {
    Interval array[] = new Interval[clips.length];
    for(int i = 0; i < clips.length; i++) 
	array[i] = new Interval(clips[i][0], clips[i][1]);
    int start = 0, result = 0;
    while( start < T ) { 
	int max = 0;
	for(int i = 0; i < array.length; i++) // Among those interval whose start is no great than start, pick the interval with maximum end as new start
	    if( array[i].start <= start )
		max = Math.max(array[i].end, max);
	if( max <= start )
	    return -1;
	start = max;
        result++;
    }
    return result;
}