题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
出处

思路

使用类似位示图的方法表示，但是对于[0,0][1,4]这种会被误认为连续，所以全部*2以做分隔。

代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int min=10001,max=0;
        bool map[20002]={0};
        int start, end;
        vector<vector<int>> ans;
        for(int i=0;i<intervals.size();i++){
            start=intervals[i][0];
            end=intervals[i][1];
            if(start<min)min=start;
            if(end>max)max=end;
            if(start==end)map[start*2]=1;//0要特殊处理
            fill(map+start*2,map+end*2+1,1);
        }
        vector<int> a={0,0};
        cout<<min<<max<<endl;
        for(int i=0;i<9;i++)cout<<map[i]<<endl;
        min=min*2;max=max*2;
        while(min<max){
            while(map[min]==0&&min<max)min++;
            a[0]=min/2;
            while (map[min]==1&&min<=max)min++;
            a[1]=min/2;
            ans.push_back(a);
        }
        return ans;
    }
};