merge interval

1）使用计数器，如果count == 1，start=curpos，如果count==0，加入当前interval

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

bool comp(const pair<int, int>& p1, const pair<int, int>& p2)
{
    if(p1.first != p2.first)
    {
        return p1.first < p2.first;
    }

    return p1.second < p2.second;
}

class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        int n = intervals.size();
        if(n == 0)
        {
            return intervals;
        }

        vector<Interval> ret;
        vector<pair<int, int>> time;
        for(Interval i : intervals)
        {
            time.push_back(make_pair(i.start, 0));
            time.push_back(make_pair(i.end, 1));
        }

        sort(time.begin(), time.end(), comp);

        int start = 0;
        int count = 0;
        for(pair<int, int> p : time)
        {
            if(p.second == 0)
            {
                count++;
                if(count == 1)
                {
                    start = p.first;
                }
            }
            else
            {
                count--;
                if(count == 0)
                {
                    ret.push_back(Interval(start, p.first));
                }
            }
        }

        return ret;
    }
};