问题描述：给你n个闭区间，输出这n个开区间的所有交区间，可能存在一个子区间有多次重复，一个交区间的定义是至少有两个大区间都包含它，并且答案集中要尽可能地把所有区间合并。注：为了避免歧义，头对尾交于一个点则不算交。

思路：这是对于LeetCode986的一个拓展，如果问题约束到一个交区间最多只有两个大区间包含它，那么就可以先把区间预处理成像LeetCode986那样的两个递增区间，用双指针求交集。

对于这个问题我们也是要用到贪心的策略，先对左端点排序，之后维护一个全局的最右上限，每次都拿左端点跟这个最右上限比较，大于它就与之前的区间互斥，更新一下上限，否则求一下交。

但是发现问题还有个条件，尽量合并答案中的子区间，也就是说如果区间是这样的[1,3]，[3, 5]则要合并起来[1,5]。对于这个问题我们可以先求所有的交区间，然后对答案集中的区间再执行像力扣56那样的并区间也是能够解决的，但感觉有些复杂了，我们还可以在线地更新：

由于我们已经对左端点排序了，当寻找到一组交地时候，后面如果发现这个左端点在上一组交区间的左边说明可以合并，于是就把它的右区间拉长，否则就添加新的一组交区间，由于按左端点排序了，当前没有与前一个交区间k产生交，后面的区间就更不可能与它产生交了，说明那个交区间已经是最优。这样实际上就解决了前面的最优子问题，后面照做就能达到全局最优，符合贪心的套路。

对于这个问题其实还有个更一般的做法，维护一个线段树，因为区间问题嘛，最后统计所有的sum大于1的点，用两个指针扫一次即可，复杂度也是，只不过这个做法常数可能会有点大

#include <bits/stdc++.h>
using namespace std;

struct interval {
    int l,r;
    bool operator < (const interval& A) const {
        return l<A.l;
    }
};

int main() {
    int n, l, r;
    vector<interval> val;
    vector<interval> ans;
    val.clear(); ans.clear(); 
    scanf("%d", &n);
    for (int i=0; i<n; i++) scanf("%d%d", &l, &r), val.push_back({l, r}); //读入
    sort(val.begin(), val.end()); //按左端点排序
    if(n) {
        r = val[0].r; //全局的右端点
        for(int i=1; i<n; i++) {
            int cur_l = val[i].l;
            int cur_r = val[i].r;
            if (cur_l >= r) //说明这个区间与之前的区间互斥，由于按左端点排序，所以之后的点也与之前的互斥,否则肯定有交区间
                r = cur_r; 
            else if (ans.size() == 0) //发现是第一个交区间，所以没有给他更新的，直接push,并维护全局右端点
                ans.push_back({cur_l, min(cur_r, r)}),r = max(r, cur_r); 
            else if (cur_r <= r) { //右端点完全被包含，之后要么扩大原来的要么增加新的要么啥都没做（之前交集的子区间），但最多只会更新到cur_r
                if (cur_l <= ans.back().r) //扩大原来的
                    ans.back().r = max(cur_r, ans.back().r); //子区间的话就不更新
                else                       //增加新的
                    ans.push_back({cur_l, cur_r});
            } else {                       //右端点不被包含，扩大的交也只能到之前的全局右端点
                if (cur_l <= ans.back().r) //扩大原来的
                    ans.back().r = max(r, ans.back().r); //子区间的话就不更新 注意右端点只能到之前的全局右端点
                else                       //增加新的
                    ans.push_back({cur_l, r});
                r = cur_r; //更新全局右端点
            }          
        }

        for (int i=0; i<ans.size(); i++)
            printf("[%d,%d]\n", ans[i].l, ans[i].r);
    }
    return 0;
}

/*
4
1 5
3 8
4 7
6 12
*/

对于像LeetCode986的交问题实际上是我们这个问题的一个特例，把所有区间加到一个数组后对左端点排序之后和我们这题一样做也能解决，相当于特殊问题一般化。注意那题相交于一点也算一个子区间。

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0]<b[0];    
    }

    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> ans; ans.clear();
        if (A.size()==0 || B.size()==0) return ans;
        for(int i=0; i<B.size(); i++) A.push_back(B[i]);
        sort(A.begin(), A.end(), cmp);
        int r = A[0][1]; //全局的右端点
        for(int i=1; i<A.size(); i++) {
            int cur_l = A[i][0];
            int cur_r = A[i][1];
            if (cur_l > r) //说明这个区间与之前的区间互斥，由于按左端点排序，所以之后的点也与之前的互斥,否则肯定有交区间(注意这个条件相交于一点也算一个区间)
                r = cur_r; 
            else if (ans.size() == 0) //发现是第一个交区间，所以没有给他更新的，直接push,并维护全局右端点
                ans.push_back({cur_l, min(cur_r, r)}),r = max(r, cur_r); 
            else if (cur_r <= r) { //右端点完全被包含，之后要么扩大原来的要么增加新的要么啥都没做（之前交集的子区间），但最多只会更新到cur_r
                if (cur_l <= ans.back()[1]) //扩大原来的
                    ans.back()[1] = max(cur_r, ans.back()[1]); //子区间的话就不更新
                else                       //增加新的
                    ans.push_back({cur_l, cur_r});
            } else {                       //右端点不被包含，扩大的交也只能到之前的全局右端点
                if (cur_l <= ans.back()[1]) //扩大原来的
                    ans.back()[1] = max(r, ans.back()[1]); //子区间的话就不更新 注意右端点只能到之前的全局右端点
                else                       //增加新的
                    ans.push_back({cur_l, r});
                r = cur_r; //更新全局右端点
            }          
        }
        return ans;
    }
};