Leetcode56. 合并区间

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

1
2
3
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

1
2
3
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示：

  • 1≤intervals.length≤1041 \leq intervals.length \leq 10^4
  • intervals[i].length==2intervals[i].length == 2
  • 0≤starti≤endi≤1040 \leq starti \leq endi \leq 10^4

解题思路

这道题的思路比较简单，首先将数组intervals按左端点的值进行排序，然后依次进行合并就行。

在解题的过程中，主要运用了以下特性：

  • 在写排序的比较函数的时候，使用了lamda表达式
  • 使用了vector::back()方法，它返回的是最后一个元素的引用

时间复杂度为：O(nlogn)O(nlogn)，其中nn为区间数量

空间复杂度为：O(logn)O(logn)，其中nn为区间数量

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<vector<int>>merge(vector<vector<int>>&intervals)
{
    if(intervals.empty()) return {};
    sort(intervals.begin(),intervals.end(),[](vector<int>&a,vector<int>&b){ return (a[0]<b[0]);});
    vector<vector<int>>ans;
    int L=intervals[0][0],R=intervals[0][1];
    ans.push_back({L,R});
    for(int i=1;i<intervals.size();++i)
    {
        if(intervals[i][0]<=ans.back()[1]&&intervals[i][1]>ans.back()[1])
        {
            ans.back()[1]=intervals[i][1];
        }
        else if(intervals[i][0]>ans.back()[1])
        {
            ans.push_back(intervals[i]);
        }
    }
    return ans;
}