浙江省火电建设公司网站/北京整站线上推广优化

链接：56. 合并区间 - 力扣（LeetCode）

这道题可以用贪心。

首先将intervals的left（intervals[i][0]）排序。

然后拿出第一个区间，比较后面相邻的区间：

当前right<后left，表示下一个区间独立了，没有与前一个区间重叠的了。

当前right<后left，表示重叠了，因为left排序了，因此right选择大的就行。

其中，在这道题里，我还学到了对于排序时的比较器函数，它有一些说法。

我首先用了自己写的静态比较器（因为sort不是类内函数，cmp如果不是静态，就会报错）（将cmp写在类外也行），但是这样的话，排序的每次比较，都会调用函数，造成开销，同时是值传递，会复制值，造成开销。因此程序运行时的速度会很慢。

但是，我们可以使用内联，增加编译的时间，减少运行的时间。可以通过以下方法内联：

1.lambda表达式

2.sort默认比较器（默认的比较器默认比较intervals[i][0]）

3.inline标记函数，注意要const。因为sort传递给比较函数的参数通常是const对象，因此函数签名与默认行为不匹配，可能导致编译器拒绝内联，甚至报错。

inline bool cmp(const vector<int>& A, const vector<int>& B) {return A[0] < B[0];
}

当然，还可以使用引用传递，避免复制值，直接传递地址，防止造成的额外开销，（其实值的复制

才是最影响效率的）

bool cmp(vector<int>& A,vector<int>& B)
{return A[0]<B[0];
}

通过比较，可以看到，这方面的优化会提升不少i的程序运行效率。

下面是我的代码：

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) {//调用自己写的比较器，尤其是静态的，不会内联。每次调用比较函数都会有额外的函数调用开销。//sort(intervals.begin(),intervals.end(),cmp);     //默认的比较器默认比较intervals[i][0]//sort(intervals.begin(),intervals.end());//lambda表达式，会内联sort(intervals.begin(), intervals.end(), [](const vector<int>& A, const vector<int>& B) {return A[0] < B[0];});vector<vector<int>> ans;vector<int> t=intervals[0];for(int i=1;i<intervals.size();i++){if(t[1]<intervals[i][0]){ans.push_back(t);t=intervals[i];}else{t[1]=max(t[1],intervals[i][1]);}}ans.push_back(t);return ans;}
};