leetcode || 56、 Merge Intervals

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