转载

LeetCode 第56题 Merge Intervals 【排序】Java

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

题目：合并间隔

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

例一：

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

例二：

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

我看第一个例子，画在图上如下：

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

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

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

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

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

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

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

原文 http://codechina.org/2019/07/leetcode-56-merge-intervals-sort-java/

正文到此结束

所属分类： Java 编程技术

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。