力扣经典150题第四十八题：合并区间

本文主要是介绍力扣经典150题第四十八题：合并区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述和要求

给定一个数组 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] 可被视为重叠区间。

解题思路

我们可以对区间按照起始位置进行排序，然后依次遍历每个区间，合并重叠的区间。具体步骤如下：

对区间按照起始位置进行排序。
初始化一个结果列表，用于存储合并后的区间。
遍历排序后的区间，如果当前区间与结果列表中最后一个区间重叠，则更新最后一个区间的结束位置；否则，将当前区间加入结果列表。
返回结果列表。

算法实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class MergeIntervals {public int[][] merge(int[][] intervals) {if (intervals == null || intervals.length == 0) {return new int[0][];}Arrays.sort(intervals, (a, b) -> a[0] - b[0]);List<int[]> merged = new ArrayList<>();for (int[] interval : intervals) {if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {merged.add(interval);} else {merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);}}return merged.toArray(new int[merged.size()][]);}
}

复杂度分析

时间复杂度：O(nlogn)，其中 n 为区间的数量。排序的时间复杂度为 O(nlogn)，遍历一次区间的时间复杂度为 O(n)。
空间复杂度：O(logn)~O(n)，取决于排序的实现方式和额外空间的使用情况。

测试和验证

编写测试用例对算法进行验证，确保其正确性和健壮性。

public class Main {public static void main(String[] args) {MergeIntervals mergeIntervals = new MergeIntervals();int[][] intervals1 = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};System.out.println(Arrays.deepToString(mergeIntervals.merge(intervals1))); // [[1,6],[8,10],[15,18]]int[][] intervals2 = {{1, 4}, {4, 5}};System.out.println(Arrays.deepToString(mergeIntervals.merge(intervals2))); // [[1,5]]}
}