分类
LeetCode刷题

LeetCode 第57题 Insert Interval 【排序】Java

原题地址:https://leetcode.com/problems/insert-interval/

题目:插入间隔

给定一组没有重叠间隔,插入一个新的间隔(如果需要合并,就合并)。

你可以假定这些间隔一开始就是有序排列的。

例一:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]

例二:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 因为新间隔 [4,8][3,5],[6,7],[8,10]都有重叠的部分。

很简单就可以看出,这道题和第56题,差异不大。所以,我的解决方法很无耻,直接调用了第56题的解法。先把新的间隔插入到间隔数组最后,然后调用56题的解法。

执行耗时3ms,虽然只比24.68%的Java提交快,但是我感觉算可以接受得了。如果认真做这道题,应该在已排序数组里面找到第一个已经重叠的间隔合并,然后继续看,直到第一个不重叠的间隔,即可退出,实现难度并不大。是会比当前实现快一些的。

代码地址:https://github.com/tinyfool/leetcode/tree/master/src/p0057

其他排序相关题目,参照排序主题

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据