LeetCode 第56题 Merge Intervals 【排序】Java

原题地址:https://leetcode.com/problems/merge-intervals/

题目:合并间隔

给定一组间隔,合并全部相互又重叠的间隔。

例一:

输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 因为[1,3]和[2,6]有重叠,把他们合并为[1,6]。

例二:

输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: [1,4]和[4,5]有重叠。

我看第一个例子,画在图上如下:

可能会有更复杂的情况,但是我们简单的发现,如果首先按照间隔的左坐标排序,这个题是比较好理解的。然后,我们每次取一个当前的间隔和下一个间隔比较,第一个间隔的右端大于等于下一个间隔的左端的话,那么这两个间隔就是有重叠部分的。那么我们就有了isOverlap函数的定义:

用来合并两个间隔的merge函数也很好写:

然后我们开始写主函数merge,首先利用Arrays.sort来排序,我们只需要实现一个compare方法,只比较间隔的左边即可:

然后,就循环处理每一个间隔,首先让第一间隔赋值给current,然后从第二间隔开始循环,如果有重叠,那么合并,结果current,如果没有,把current扔进结果集,当前间隔赋值给current。

最后把ArrayList的数据变成一个数组输出。

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

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

打赏

2 thoughts to “LeetCode 第56题 Merge Intervals 【排序】Java”

  1. 第一个间隔的右端小于等于下一个间隔的左端的话

    应改为

    第一个间隔的右端大于等于下一个间隔的左端的话

发表评论

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

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