题目描述
以数组 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;
}
};