剪视频剪出一个贪心算法

int videoStitching(int[][] clips, int T);

class Solution {
    public int videoStitching(int[][] clips, int T) {
        if (T == 0) return 0;
        // 按起点升序排列，起点相同的降序排列
        Arrays.sort(clips, (a, b) -> {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        // 记录选择的短视频个数
        int res = 0;

        int curEnd = 0, nextEnd = 0;
        int i = 0, n = clips.length;
        while (i < n && clips[i][0] <= curEnd) {
            // 在第 res 个视频的区间内贪心选择下一个视频
            while (i < n && clips[i][0] <= curEnd) {
                nextEnd = Math.max(nextEnd, clips[i][1]);
                i++;
            }
            // 找到下一个视频，更新 curEnd
            res++;
            curEnd = nextEnd;
            if (curEnd >= T) {
                // 已经可以拼出区间 [0, T]
                return res;
            }
        }
        // 无法连续拼出区间 [0, T]
        return -1;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        if (T == 0) return 0;
        // 按起点升序排列，起点相同的降序排列
        sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) {
            if (a[0] == b[0]) {
                return b[1] - a[1];
            }
            return a[0] - b[0];
        });
        // 记录选择的短视频个数
        int res = 0;

        int curEnd = 0, nextEnd = 0;
        int i = 0, n = clips.size();
        while (i < n && clips[i][0] <= curEnd) {
            // 在第 res 个视频的区间内贪心选择下一个视频
            while (i < n && clips[i][0] <= curEnd) {
                nextEnd = max(nextEnd, clips[i][1]);
                i++;
            }
            // 找到下一个视频，更新 curEnd
            res++;
            curEnd = nextEnd;
            if (curEnd >= T) {
                // 已经可以拼出区间 [0, T]
                return res;
            }
        }
        // 无法连续拼出区间 [0, T]
        return -1;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        if T == 0:
            return 0
        # 按起点升序排列，起点相同的降序排列
        clips.sort(key=lambda a: (a[0], -a[1]))
        # 记录选择的短视频个数
        res = 0

        curEnd = 0
        nextEnd = 0
        i = 0
        n = len(clips)
        while i < n and clips[i][0] <= curEnd:
            # 在第 res 个视频的区间内贪心选择下一个视频
            while i < n and clips[i][0] <= curEnd:
                nextEnd = max(nextEnd, clips[i][1])
                i += 1
            # 找到下一个视频，更新 curEnd
            res += 1
            curEnd = nextEnd
            if curEnd >= T:
                # 已经可以拼出区间 [0, T]
                return res
        # 无法连续拼出区间 [0, T]
        return -1

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

func videoStitching(clips [][]int, T int) int {
    if T == 0 {
        return 0;
    }

    // 按起点升序排列，起点相同的降序排列
    sort.Slice(clips, func(i, j int) bool {
        if clips[i][0] == clips[j][0] {
            return clips[j][1] < clips[i][1]
        } else {
            return clips[i][0] < clips[j][0]
        }
    })

    // 记录选择的短视频个数
    res, curEnd, nextEnd := 0, 0, 0
    for i := 0; i < len(clips) && clips[i][0] <= curEnd; {
        // 在第 res 个视频的区间内贪心选择下一个视频
        for ; i < len(clips) && clips[i][0] <= curEnd; i++ {
            nextEnd = max(nextEnd, clips[i][1])
        }
        // 找到下一个视频，更新 curEnd
        res++
        curEnd = nextEnd
        if curEnd >= T {
            // 已经可以拼出区间 [0, T]
            return res
        }
    }
    // 无法连续拼出区间 [0, T]
    return -1
}

func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var videoStitching = function(clips, T) {
    if (T === 0) return 0;
    // 按起点升序排列，起点相同的降序排列
    clips.sort((a, b) => {
        if (a[0] === b[0]) {
            return b[1] - a[1];
        }
        return a[0] - b[0];
    });
    // 记录选择的短视频个数
    let res = 0;

    let curEnd = 0, nextEnd = 0;
    let i = 0, n = clips.length;
    while (i < n && clips[i][0] <= curEnd) {
        // 在第 res 个视频的区间内贪心选择下一个视频
        while (i < n && clips[i][0] <= curEnd) {
            nextEnd = Math.max(nextEnd, clips[i][1]);
            i++;
        }
        // 找到下一个视频，更新 curEnd
        res++;
        curEnd = nextEnd;
        if (curEnd >= T) {
            // 已经可以拼出区间 [0, T]
            return res;
        }
    }
    // 无法连续拼出区间 [0, T]
    return -1;
};