原题地址: 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题的解法。
执行耗时3ms,虽然只比 24.68% 的Java提交快,但是我感觉算可以接受得了。如果认真做这道题,应该在已排序数组里面找到第一个已经重叠的间隔合并,然后继续看,直到第一个不重叠的间隔,即可退出,实现难度并不大。是会比当前实现快一些的。
代码地址: https://github.com/tinyfool/leetcode/tree/master/src/p0057
其他排序相关题目,参照排序主题。