原文链接: https://leetcode-cn.com/problems/merge-intervals

英文原文

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Constraints:

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

中文题目

以数组 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

通过代码

高赞题解

前言：

今天的打卡题是「56. 合并区间」，以本题为依据，我把力扣上另外 3 道类似的区间题目整理在了一起，供大家查阅。
除了这 4 道题目之外，另外补充了 1 道区间相关的双指针/滑动窗口题目，及 1 道最长上升子序列的区间变种题目。
🤷‍♀️必须秒懂力扣区间题目：重叠区间、合并区间、插入区间

一、合并 2 个区间

2 个区间的关系有以下 6 种，但是其实可以变成上面 3 种情况（只需要假设 第一个区间的起始位置 $\leq$ 第二个区间的起始位置，如果不满足这个假设，交换这两个区间）。这 3 种情况的合并的逻辑都很好写。

二、合并 n 个区间

先根据区间的起始位置排序，再进行 $n -1$ 次 两两合并。

代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        // 先按照区间起始位置排序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval: intervals) {
            // 如果结果数组是空的，或者当前区间的起始位置 > 结果数组中最后区间的终止位置，
            // 则不合并，直接将当前区间加入结果数组。
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                // 反之将当前区间合并至结果数组的最后区间
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }
}

❤️ 大佬们随手赏个「爱心赞」吧，如果能随手关注下我的公众号【甜姨的奇妙冒险】和 知乎专栏【甜姨的力扣题解】就更好了啊 ▄█▔▉●

🔥昨天的打卡题「01 矩阵」，已在公众号和专栏更新，一文秒懂多源BFS，求戳！👆

统计信息

通过次数	提交次数	AC比率
330357	698679	47.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
插入区间	中等
会议室	简单
会议室 II	中等
提莫攻击	简单
给字符串添加加粗标签	中等
Range 模块	困难
员工空闲时间	困难
划分字母区间	中等
区间列表的交集	中等