合并区间 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);