HHot 100C++ 图解

56. 合并区间

中等 普通数组 在力扣上做

一句话套路按左端排序 + 合并相交区间

题目描述

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

示例 3:

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

 

提示:

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

思路

时间O(n log n)
空间O(log n)

思路

按左端点排序后,只需要和「结果里最后一个区间」比:新区间左端 > 上一个的右端 -> 开新段;否则取 max 扩右端。

易错

合并时必须用 max(r, itv[1]),因为存在 [1,10],[2,3] 这种被包含的情况。

图解

j0 j1 i0 1 3 i1 2 6 i2 8 10 i3 15 18
矩阵(来自本仓库测试数据,红色格子 = 0)

C++17 题解

src/05_array.cpp17 行
namespace lc0056 {
class Solution {
 public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
    vector<vector<int>> ans;
    for (const auto& itv : intervals) {
      if (!ans.empty() && itv[0] <= ans.back()[1])
        ans.back()[1] = max(ans.back()[1], itv[1]);
      else
        ans.push_back(itv);
    }
    return ans;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q56_merge_intervals7 行
lc0056::Solution s;
vector<vector<int>> a{{1, 3}, {2, 6}, {8, 10}, {15, 18}};
CHECK_EQ(s.merge(a), vector<vector<int>>({{1, 6}, {8, 10}, {15, 18}}));
vector<vector<int>> b{{1, 4}, {4, 5}};  // 端点相接也要合并
CHECK_EQ(s.merge(b), vector<vector<int>>({{1, 5}}));
vector<vector<int>> c{{1, 10}, {2, 3}};  // 包含关系,考验 max
CHECK_EQ(s.merge(c), vector<vector<int>>({{1, 10}}));

↑↓ 选择↵ 打开/ 随时唤起