Leetcode56. 合并区间

2021年4月25日 538点热度 1人点赞 0条评论

题目描述

以数组 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 \leq intervals.length \leq 10^4$
  • $intervals[i].length == 2$
  • $0 \leq starti \leq endi \leq 10^4$

解题思路

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

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

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

时间复杂度为:$O(nlogn)$,其中$n$为区间数量

空间复杂度为:$O(logn)$,其中$n$为区间数量

示例代码

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;
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

您需要 登录 之后才可以评论