#include <vector>
#include <iostream>

using namespace std;

struct Interval 
{
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s=0, int e=0) : start(s), end(e) {}
};
void PrintIntervals(vector<Interval>& v)
{
    for (int i = 0; i < v.size(); ++i)
        cout << '[' << v[i].start << ',' << v[i].end << "], ";
    
    cout << endl;
}
void Merging(vector<Interval> &intervals, int low, int mid, int high)
{
    vector<Interval> temp;
    temp.reserve(high - low);

    int i = low;
    int j = mid;

    while(i < mid && j < high)
    {
        Interval interI = intervals[i];
        Interval interJ = intervals[j];

        if (interI.start < interJ.start 
            || (interI.start == interJ.start && interI.end < interJ.end))
        {
            temp.push_back(interI);
			++i;
        }
        else 
		{
			temp.push_back(interJ);
			++j;
		}
    }

    while(i < mid)
        temp.push_back(intervals[i++]);

    while(j < high)
        temp.push_back(intervals[j++]);

    for (int i = 0; i < temp.size(); ++i)
        intervals[low+i] = temp[i];
}

//Sort elements in [low, high)
void MergeSort(vector<Interval> &intervals, int low, int high)
{
    if(low >= high-1) return;

    int mid = (low + high) / 2;
    MergeSort(intervals, low, mid);
    MergeSort(intervals, mid, high);

    Merging(intervals, low, mid, high);
}

vector<Interval> MergeIntervals(vector<Interval> &intervals) 
{
    if (intervals.size() <= 1)return intervals;
    vector<Interval> result;

    //sort the intervals by start, end
    MergeSort(intervals, 0, intervals.size());
	
    result.push_back(intervals.front());

    for (int i = 1; i < intervals.size(); ++i)
    {
        Interval& cur = intervals[i];
        Interval& pre = result.back();

        if (pre.end < cur.start) //no overlaping of two intervals
            result.push_back(cur);

        else 
            if(pre.end < cur.end)
            pre.end = cur.end;
        
        //else  if(pre.end == cur.end) //do nothing
       
    } 

    return result;       
}






int main(int argc, char** argv)
{
    //[1,3], [6,9], [2,5]; 
    vector<Interval> v1;
    v1.push_back(Interval(1,3));
    v1.push_back(Interval(6,9));
    v1.push_back(Interval(2,5));

    vector<Interval> r1 = MergeIntervals(v1);
    PrintIntervals(r1); //[1,5],[6,9]
    
    return 0;
}