leetcode_56 合并区间

1. 题意

给一个区间集合，求对有交集合的区间合并后的区间。

2. 题解

2.1 排序+双指针

为什么需要对数据进行排序，
为什么是对区间起点进行排序？
对区间终点进行排序行不行？

实际上对于两个区间$[l_1,r_1][l_2,r_2]$， 我们只需要他们满足
$$l_1\le r_2,l_2\le r_1$$
两个条件即可。

而无论是按照区间的起点，还是按照区间的终点进行排序。 我们都是在保证其中一个条件。

如果按区间左端点排序，它保证$l_1\le l_2\wedge l_2\le r_2\Rightarrow l_1\le r_2$。
如果按区间右端点排序，它保证了$r_1\le r_2\wedge l_1\le r_1\Rightarrow l_1\le r_2$。

再谈官解里面的正确性证明；为什么存在$a[i],a[k]$本应该合并，一定会存在三元组$i,j,k(i<j<k)$, 满足$a[i],a[j]$不能合并，且$a[j],a[k]$不能合并。

首先$i,k$肯定是不相邻的，如果相邻的话就不是异常情况了，所以$i,k$之间存在其他整数；

其次为什么一定是$a[i],a[j]$不能合并且$a[j],a[k]$也不能合并。

因为$a[i],a[j]$合并后一定是包含$a[i]$，因此必然可以和$a[k]$合并的；
同理$a[j],a[k]$合并后一定是包含$a[k]$, 因此必然可以和$a[i]$合并的。

因此$a[j]$与$a[i],a[k]$都不能合并。

因此必有
$$\begin{gathered} a[i].r<a[j].l \\ a[j].r<a[k].l \end{gathered}$$
进而
$$\begin{gathered} a[j].l<a[j].r \\ a[i].r<a[k].l \end{gathered}$$
这与$a[i],a[k]$相交
$$a[i].r\ge a[k].l$$
矛盾。

按右端点排序时，我们需要反着来处理。

因为正序无法处理[1,2] [3,5] [2,6]这样的情况。

• 按左端点排序

class Solution {
public:


    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        sort( intervals.begin(), intervals.end(), [](const std::vector<int> &a, const std::vector<int> &b)
        {
            if ( a[0] != b[0])
                return a[0] < b[0];
            return a[1] < b[1];
        });

        for ( auto it = intervals.begin(); it != intervals.end(); ) {
            
            auto lst = it + 1;  
            while (lst != intervals.end() && (*lst)[0] <= (*it)[1] ) {
                (*it)[1] = std::max((*it)[1], (*lst)[1]);
                ++lst;
            }

            if (lst != it + 1) {
                it = intervals.erase( it + 1, lst);
            }
            else {
                ++it;
            }
        }

        return intervals;
    }
};

• 按右端点排序

class Solution {
public:


    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        
        sort( intervals.begin(), intervals.end(),[](const std::vector<int> &a,
            const std::vector<int> &b){
            if ( a[1] != b[1]) {
                return a[1] < b[1];
            }
            return a[0] < b[0];
        });

        std::vector<std::vector<int>> ans;

        int sz = intervals.size();
        int cur = 0;
        int lst{0};
        for (int i = intervals.size() - 1;i > -1; i = lst) {
            cur = i;
            lst = i - 1;

            while ( lst > -1 && intervals[cur][0] <= intervals[lst][1]) {
                intervals[cur][0] = std::min( intervals[cur][0], intervals[lst][0]);
                --lst;
            }
            ans.insert( ans.begin(), intervals[cur]); 
        }

        return ans;
    }
};

2.2 差分数组

使用差分数组标记来处理一整片，当出现连续的正数的时候说明是一整个区间。

但有个问题是，似乎无法处理$[1,2][3,4]$这样的情况；

灵之一手的是，直接把区间给扩大到原来两倍，这样不相交区间之间的距离最少就成2了，上面那种情况就不会出现了。

实在是妙！

class Solution {
public:


    vector<vector<int>> merge(vector<vector<int>>& intervals) {

        vector<int> diff(2e4+4, 0);

        int mx = 0;
        for (auto ints: intervals) {
            diff[ 2 * ints[0] ]++;
            diff[ 2 * ints[1] + 1]--;
            mx = std::max(mx, ints[1]);
        }

        int cur = 0;

        vector< vector<int>> ans;

        vector<int> tmp(2, 0);
        for (int i = 0;i <= 2 * mx + 1; ++i) {
            if ( cur == 0 && diff[i] > 0) {
                tmp[0] = i / 2;
            }
            else if (cur > 0 && (diff[i] + cur == 0) ) {
                tmp[1] = (i - 1) / 2;
                ans.push_back( tmp);
            }
            cur += diff[ i ];
        }

        return ans;
    }
};

参考

leetcode-官解
03xf的题解