LeetCode 1024. 视频拼接

Categories:

题目描述
思路分析
1. 解法一：贪心选择最远覆盖（推荐）
相似题目

题目描述

✅ 1024. 视频拼接

思路分析

解法一：贪心选择最远覆盖（推荐）

核心思路：

将区间按起点升序排序，维护当前已覆盖的右端 curEnd。

扫描所有起点不超过 curEnd 的片段，更新最远可达 farthest。

当扫描结束仍无法扩展时说明不可达；否则计数并推进到 farthest。

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示片段数量。

空间复杂度：O(1)，排序额外空间不计入。

import java.util.Arrays;

class Solution {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);

        int res = 0;
        int curEnd = 0;
        int farthest = 0;
        int i = 0;

        while (curEnd < time) {
            // 在能接上的区间里尽量扩展最远覆盖
            while (i < clips.length && clips[i][0] <= curEnd) {
                farthest = Math.max(farthest, clips[i][1]);
                i++;
            }
            if (farthest == curEnd) {
                return -1;
            }
            res++;
            curEnd = farthest;
        }

        return res;
    }
}

import "sort"

func videoStitching(clips [][]int, time int) int {
	sort.Slice(clips, func(i, j int) bool {
		if clips[i][0] == clips[j][0] {
			return clips[i][1] < clips[j][1]
		}
		return clips[i][0] < clips[j][0]
	})

	res := 0
	curEnd := 0
	farthest := 0
	idx := 0

	for curEnd < time {
		// 在能接上的区间里尽量扩展最远覆盖
		for idx < len(clips) && clips[idx][0] <= curEnd {
			if clips[idx][1] > farthest {
				farthest = clips[idx][1]
			}
			idx++
		}
		if farthest == curEnd {
			return -1
		}
		res++
		curEnd = farthest
	}

	return res
}

相似题目

题目	难度	考察点
45. 跳跃游戏 II	中等	贪心
55. 跳跃游戏	中等	贪心
1326. 灌溉花园的最少水龙头数	困难	贪心
435. 无重叠区间	中等	区间贪心
452. 用最少数量的箭引爆气球	中等	区间贪心

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/48712250