Leetcode 56. 合并区间

开发者 · 2024-10-3 08:04:47

标题要求

以数组 intervals 表现多少个区间的聚集，此中单个区间为 intervals = [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] 可被视为重叠区间。

解题思路

起首对区间按照左端点由小到大排序，再举行区间合并，长处是：

可以包管左端点是最左边的点，每次合并可以固定左端点，只判断右端点是否重叠

数组排序的写法：
// 由小到大排序 Arrays.sort(intervals, (o1, o2) -> { return o1[0] - o2[0]; });合并区间的步调，看下面的源码就可以，比力好懂：

先选择第一个区间，加入list

比力之后的区间与之是否有重叠，假如有重叠则合并两个区间，将新区间加入list

假如不重叠，则将新区间加入list

每次合并都选择list中末了一个区间

Java题解

Leetcode 56. 合并区间

所属分类: 问答交流

新帖推荐: 30日

推荐作品