leetcode || 56、 Merge Intervals

problem:

?

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

?

?

thinking:

（1）一开始我想到用hash table的方法，开一个总区间跨度的数组，对于有区间覆盖的数组区间置为true，没被覆盖的数组区间置为false，最后将true区间的起点和终点作为区间输出即可。思路简单，但是，我忽略一个问题：区间跨度是不定的，所以要开的数组大小有可能很大。提交也显示：Memory Limit Exceeded

（2）换一种方法，排序法。

可以直接对vector 数组排序，要重载compare函数。也可以使用multimap ,注意不是map

?

code:

排序法： Accepted

?

class Solution {
public:
    vector
  
    merge(vector
   
     &intervals) { vector
    
      ret; multimap
     
       map_intervals; if(intervals.size()==0) return ret; if(intervals.size()==1) return intervals; for(vector
      
       ::iterator it=intervals.begin();it!=intervals.end();it++) map_intervals.insert(make_pair((*it).start,(*it).end)); multimap
       
        ::iterator p=map_intervals.begin(); Interval tmp(p->first,p->second); for(multimap
        
         ::iterator k=++p;k!=map_intervals.end();k++) { if(k->first<=tmp.end) tmp.end=max(tmp.end,k->second); else { ret.push_back(tmp); tmp.start=k->first; tmp.end=k->second; } } ret.push_back(tmp); return ret; } }; 
        
       
      
     
    
   
  

?

?

class Solution {
public:
    vector
  
    merge(vector
   
     &intervals) { vector
    
      ret; int first=INT_MAX, last=INT_MIN; for(vector
     
      ::iterator tmp=intervals.begin();tmp!=intervals.end();tmp++) { first=min((*tmp).start,first); last=max((*tmp).end,last); } int count=last-first+1; bool *a = new bool[count]; memset(a,false,sizeof(bool)*count); for(vector
      
       ::iterator it=intervals.begin();it!=intervals.end();it++) { int num=(*it).end-(*it).start+1; memset(a+(*it).start,true,sizeof(bool)*num); } int interval_start=0,interval_end=0; while(interval_end
       
        
?