合并区间 leetcode56

---

目录

一、题目

二、踩坑过程

一开始想使用一个数组来标记区间，但是仔细想不好实现，单纯把区间里出现的设置为1，不好体现重叠的概念，如果使用三种状态，-1表示区间起始，-2表示区间结束，区间中间的数的用大于零的数字表示，但是如果一个区间只有一个值，就不好统一了，状态变化的情况太多，而且最后不好收集所有的区间。

。。。看了解析，思路其实抓住两点，一个是两个区间之间的关系，仔细思考有6种情况（自己想）
如果把区间按起始点进行排序，位置关系有3种（自己想）

二是如何收集结果，如果第二个区间是在内部或者是有交集的情况，这个时候可以进行合并，如果是分离的情况，前一个区间就可以加入结果集了。（为什么？因为前面按起始点排序了，此时不会出现第二个区间在第一个区间左边的情况）

------> 感悟：自己死磕区间标记搞了两个小时，最后被1个用例卡住了，含泪放弃自己的思路了。
😭

三、上官方解答

#include<iostream>
#include<vector>
#include<algorithm>using namespace std;class Solution {
public:static bool cmp(vector<int> v1, vector<int> v2) {return v2[0] > v1[0];}int RelPosition(vector<int> v1, vector<int> v2) {// 相离if (v2[0] > v1[1]) {return 3;}// 包含if (v2[0] >= v1[0] && v2[1] <= v1[1]) {return 1;}// 交集if (v2[0] >= v1[0] && v2[0] <= v1[1] && v2[1] >= v1[1]) {return 2;}return -1;}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), cmp);vector<vector<int>> res;vector<int> tmpres;tmpres = intervals[0];for (int i = 1; i < intervals.size(); i++) {vector<int> intv = intervals[i];int p = RelPosition(tmpres, intv);if (p == 3) {res.push_back(tmpres);tmpres = intv;} else if (p == 2) {tmpres[1] = intv[1];}}res.push_back(tmpres);return res;}
};

四、含泪体会

这道题的提交记录有十几次，但是这次还是没有写出来，😭，因为之前的提交是直接看的答案，第一反应还是直接标记数组解决，结果坑了啊，坑了啊。。。

彩蛋

因为工作语言用的是C，发现qsort和sort的cmp函数有点不一样，总结一下。
c语言中的qsort升序

// 比较函数，用于比较两个整数
int cmpfunc (const void * a, const void * b)
{return ( *(int*)a - *(int*)b ); // 从小到大
}
qsort((void*)arr, size, sizeof(arr[0]), cmpfunc);

c++中sort升序

bool cmp(int a ,int b)
{return a < b ;		// 从小到大排序，把 < 换成 > 就是从大到小 
}
sort(p.begin(), p.end(), cmp);