package question1024_video_stitching;

import java.util.Arrays;

/**
 * 先对区间进行排序，比较原则为先比较每个区间的起点，再比较每个区间的终点。
 *
 * 依次遍历排序后的每个区间，取满足条件的终点最大的那个区间作为选取的下一个区间。如果在遍历过程中无法找到下一个满足条件的区间，返回 -1。
 *
 * 时间复杂度是 O(logn)，其中 n 为 clips 数组的长度。空间复杂度是 O(1)。
 *
 * 执行用时：1ms，击败74.47%。消耗内存：37.3MB，击败100.00%。
 */
public class Solution {

    public int videoStitching(int[][] clips, int T) {
        Arrays.sort(clips, (clip1, clip2) -> {
            if (clip1[0] == clip2[0]) {
                return clip1[1] - clip2[1];
            }
            return clip1[0] - clip2[0];
        });
        if (clips.length == 0 || clips[0][0] != 0 || clips[clips.length - 1][1] < T) {
            return -1;
        }
        int end = 0, result = 0;
        for (int i = 0; i < clips.length; i++) {
            if (clips[i][0] <= end) {
                int candidate = i, j = i;
                while (j + 1 < clips.length && clips[j + 1][0] <= end) {
                    j++;
                    if (clips[j][1] > clips[candidate][1]) {
                        candidate = j;
                    }
                }
                result++;
                if (clips[candidate][1] >= T) {
                    return result;
                }
                i = j;
                end = clips[candidate][1];
            } else {
                return -1;
            }
        }
        return result;
    }

}