转载

LeetCode 第57题 Insert Interval 【排序】Java

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

题目:插入间隔

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

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

例一:

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

例二:

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

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

LeetCode 第57题 Insert Interval 【排序】Java

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

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

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

原文  http://codechina.org/2019/07/leetcode-57-insert-interval-sort-java/
正文到此结束
Loading...