Leetcode 每日一题 56.合并区间

问题描述

示例

示例 1

示例 2

问题分析

算法设计

步骤 1：排序

步骤 2：合并区间

步骤 3：返回结果

过题图片

代码实现

复杂度分析

题目链接

结语

问题描述

给定一个区间数组 intervals，其中每个区间由两个整数 start 和 end 组成，表示区间的起始和结束位置。任务是合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例

示例 1

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]

示例 2

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]

问题分析

要解决这个问题，我们需要找到所有重叠的区间并将它们合并。一个直观的方法是按照区间的起始位置对区间进行排序，然后逐个检查每个区间是否与前一个区间重叠。如果重叠，我们就合并它们；如果不重叠，我们就将当前区间添加到结果数组中。

算法设计

步骤 1：排序

首先，我们需要对区间数组进行排序，排序依据是区间的起始位置。这可以通过使用 Java 的 Arrays.sort 方法和自定义的比较器来实现。

步骤 2：合并区间

接下来，我们遍历排序后的区间数组，并使用一个列表来存储合并后的区间。对于每个区间，我们检查它是否与列表中最后一个区间重叠。如果它们不重叠（即当前区间的起始位置大于列表中最后一个区间的结束位置），我们就将当前区间添加到列表中。如果它们重叠，我们就更新列表中最后一个区间的结束位置，使其成为当前区间和列表中最后一个区间结束位置的最大值。

步骤 3：返回结果

最后，我们将列表转换为数组并返回，这就是合并后不重叠的区间数组。

过题图片

代码实现

以下是使用 Java 语言实现的代码：

java

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;class Solution {public int[][] merge(int[][] intervals) {// 步骤 1：排序Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));// 步骤 2：合并区间List<int[]> res = new ArrayList<>();for (int[] interval : intervals) {if (res.isEmpty() || res.get(res.size() - 1)[1] < interval[0]) {// 如果列表为空或者当前区间不与最后一个区间重叠，添加到列表res.add(interval);} else {// 如果重叠，合并区间res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], interval[1]);}}// 步骤 3：返回结果return res.toArray(new int[res.size()][]);}
}

复杂度分析

时间复杂度：O(n log n)，其中 n 是区间的数量。主要时间消耗在排序上。
空间复杂度：O(n)，用于存储合并后的区间数组。

题目链接

56. 合并区间 - 力扣（LeetCode）

结语

合并区间问题是一个经典的算法问题，它考察了对数组操作和排序算法的理解和应用。以下是解决这类问题的一般步骤和策略：

理解问题：首先要清楚地理解问题的要求，即合并所有重叠的区间，并确保合并后的区间覆盖所有原始区间。明确输入和输出的格式。
排序：大多数情况下，解决合并区间问题的第一步是对区间进行排序。通常根据区间的起始位置进行排序，这样可以使得重叠的区间在数组中相邻，便于后续处理。
遍历合并：排序完成后，遍历排序后的区间数组，使用一个额外的数据结构（如列表）来存储合并后的区间。对于每个区间，判断它是否与前一个合并区间重叠。如果重叠，更新合并区间的结束位置；如果不重叠，将当前区间添加到结果中。
处理边界情况：在遍历过程中，要注意处理边界情况，比如当结果列表为空时，直接添加第一个区间；当当前区间不与前一个区间重叠时，也需要将当前区间添加到结果列表中。
返回结果：遍历完成后，将存储合并区间的列表转换为所需的输出格式（如数组），并返回。