【做一道算一道】 合并区间

合并区间

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

思路

自己思路就是先排序，再遍历，中间只要在区间范围内的就更新区间，出现不在区间内的就把这个区间计入答案，再把新的区间记录下来，继续遍历。
做是做出来了，看完卡尔哥这个码，思路更进一步，排序之后直接比较区间末端，太简洁了。
还有不太熟的lambda表达式，记一下

代码

我的啰嗦版本

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b){
        return a[0]<b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if(intervals.size()<2) return intervals;

        sort(intervals.begin(),intervals.end(),cmp);

        int start=intervals[0][0];
        int end=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]>=start && intervals[i][0]<=end){
                start=min(intervals[i][0],start);
                end=max(intervals[i][1],end);
            }else{
                res.push_back({start,end});
                start=intervals[i][0];
                end=intervals[i][1];
            }
        }
        res.push_back({start,end});
        return res;
    }
};

代码随想录：合并区间

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});

        // 第一个区间就可以放进结果集里，后面如果重叠，在result上直接合并
        result.push_back(intervals[0]); 

        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]); 
            } else {
                result.push_back(intervals[i]); // 区间不重叠 
            }
        }
        return result;
    }
};

补充：Lambda表达式

Lambda表达式（也称为匿名函数）是C++11标准引入的一种方便的语法，它允许你在需要一个函数对象的地方快速定义一个函数。Lambda表达式提供了一种简洁的方式来创建小型、匿名的函数对象，而不需要按照传统的语法定义一个完整的函数。

Lambda表达式的一般语法如下：

[捕获子句](参数列表) -> 返回类型 { 函数体 }

捕获子句：允许你从外部作用域捕获变量，可以是值捕获（x）或引用捕获（&x）。如果不提供捕获子句，默认情况下，lambda表达式不能访问外部变量。
参数列表：定义lambda表达式可以接受的参数，与普通函数参数列表类似。
返回类型：可以指定lambda表达式的返回类型。如果不指定，编译器会根据函数体自动推导返回类型。
函数体：定义了lambda表达式的行为，即当调用这个lambda表达式时执行的代码。
Lambda表达式可以用于多种场景，包括但不限于：

用作函数参数，例如std::sort或std::for_each的比较函数。
作为回调函数。
在并行算法中使用，如std::for_each的并行版本std::for_each_n。
下面是一些Lambda表达式的示例：

1. 简单的Lambda表达式，没有参数，没有捕获外部变量：

[]() {
    cout << "Hello, World!" << endl;
}();

2. Lambda表达式捕获外部变量：

int x = 5;
[&x]() {
    cout << "x is " << x << endl;
}();

3. Lambda表达式作为函数参数：

vector<int> v = {1, 2, 3, 4};
sort(v.begin(), v.end(), [](int a, int b) {
    return a < b;
});

4. Lambda表达式指定返回类型：

auto add = [](int a, int b) -> int {
    return a + b;
};

Lambda表达式是C++中一个非常强大的特性，它提供了一种灵活且简洁的方式来定义和使用小型函数。