乐趣区

关于程序员:剪视频剪出一个贪心算法…

读完本文,能够去力扣解决如下题目:

1024. 视频拼接(Medium


后面发过 几个视频,也算是对视频剪辑入了个门。像我这种非专业剪辑玩家,不做什么巨大特效电影镜头,只是做个视频教程,其实也没啥难度,只须要把视频剪晦涩,所以用到最多的性能就是切割性能,而后删除和拼接视频片接。

没有剪过视频的读者可能不晓得,在罕用的剪辑软件中视频被切割成若干片段之后,每个片段都能够还原成原始视频。

就比方一个 10 秒的视频,在两头切一刀剪成两个 5 秒的视频,这两个五秒的视频各自都能够还原成 10 秒的原视频。就如同蚯蚓,把本人切成 4 段就能搓麻,把本人切成 11 段就能够凑一个足球队。

剪视频时,每个视频片段都能够形象成了一个个区间,工夫就是区间的端点,这些区间有的相交,有的不相交……

假如剪辑软件不反对将视频片段还原成原视频,那么如果给我若干视频片段,我怎么将它们还原成原视频呢?

这是个很有意思的区间算法问题,也是力扣第 1024 题「视频拼接」,题目如下:

函数签名如下:

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

记得以前写过好几篇区间相干的问题:

贪婪算法玩跳跃游戏 写的跳跃游戏是雷同的,如果你能看出这两者的分割,就能够说了解贪婪算法的奥义了。

代码实现

实现上述思路须要咱们用两个变量 curEndnextEnd来进行:

最终代码实现如下:

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;
}

这段代码的工夫复杂度是多少呢?尽管代码中有一个嵌套的 while 循环,但这个嵌套 while 循环的工夫复杂度是 O(N)。因为当i 递增到 n 时循环就会完结,所以这段代码只会执行 O(N) 次。

然而别忘了咱们对 clips 数组进行了一次排序,耗费了 O(NlogN) 的工夫,所以本算法的总工夫复杂度是O(NlogN)

最初说一句,我去 B 站做 up 了,B 站搜寻同名账号「labuladong」即可关注

查看更多优质算法文章 点击这里,手把手带你刷力扣,致力于把算法讲清楚!我的 算法教程 曾经取得 90k star,欢送点赞!

退出移动版