Leetcode刷题100天—56. 合并区间( 排序)—day37

男娘i 2022-09-14 09:54 147阅读 0赞

前言：

> 作者：神的孩子在歌唱
> 
> 大家好，我叫运智

![image-20210913215450823][]

#### [56. 合并区间][56.] ####

难度中等1099收藏分享切换为英文接收动态反馈

以数组 `intervals` 表示若干个区间的集合，其中单个区间为 `intervals[i] = [starti, endi]` 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

**示例 1：**

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
    输出：[[1,6],[8,10],[15,18]]
    解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

**示例 2：**

输入：intervals = [[1,4],[4,5]]
    输出：[[1,5]]
    解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

**提示：**

*  `1 <= intervals.length <= 104`
 *  `intervals[i].length == 2`
 *  `0 <= starti <= endi <= 104`

package 排序;
    
    import java.util.List;
    import java.util.ArrayList;
    import java.util.Arrays;
    
    /* * https://leetcode-cn.com/problems/merge-intervals/ */
    public class _56_合并区间 { 
        public int[][] merge(int[][] intervals) { 
    // 如果长度为零直接返回
        	if (intervals.length==0) { 
    			return new int[0][2];
    		}
    // 先排序,按照start排列
            Arrays.sort(intervals,(a,b)->a[0]-b[0]);
    // 定义一个列表
            List<int[]> list=new ArrayList<int[]>();
    // 通过for循环遍历数组,如果前一个数组得end比第二个数组得start小，
    // 说明两个没有集合，直接存入list,否则就要获取他们end最大得数合并
            for(int[] interval:intervals) { 
    // 刚开始如果list为空就先进入，前一个数组得end比第二个数组得start小，也加入因为没有集合
            	if (list.isEmpty()||list.get(list.size()-1)[1]<interval[0]) { 
    				list.add(interval);
    			}
    // 否则就是他们有集合，合并他们两个数存入list
            	else { 
    // 修改end的值
            		list.get(list.size()-1)[1]=Math.max(list.get(list.size()-1)[1], interval[1]);
            	}
            }
    // 最后将其变成二维数组输出
        	return list.toArray(new int[list.size()][]);
       }
    }

> 本人csdn博客：https://blog.csdn.net/weixin\_46654114
> 
> 转载说明：跟我说明，务必注明来源，附带本人博客连接。

[image-20210913215450823]: /images/20220828/a4d8aa94aba34acfb2d75163fdedc8d2.png
[56.]: https://leetcode-cn.com/problems/merge-intervals/