**Description:**

https://leetcode.com/problems/merge-intervals/#/description

**Algorithm:**

Use [1,3],[2,6],[8,10],[15,18] as example

Firstly use map to take record of the intervals. Remember to initialize the map to INT_MIN and then start recording.

Let mapping->second = max(mapping->second, interval[i].end);

We do this to avoid the situation that the new interval and old interval have the same start so the end of old interval is erased in the mapping. e.g intervals = [ [2,3], [2,2], [5,5] ] . The end of [2,3] is replaced by the end of [2,2]

_-____-____-__________-________-______-________-______-___

1 2 3 6 8 10 15 18

From the first, start = 1, end = 3

The second pair: begin2 = 2 <= end = 3, end = max(end1, end2) = end2 = 6 /*Here it must be if (it->first <= end)*/

The third pair: begin3 = 8 > end = 6, push back(begin = 1, end = 6) and let begin = begin3 = 8, end = end3 = 10

The fourth pair: begin4 = 15 > end = 10, push back(begin = 8, end = 10) and let begin = begin4 = 15, end = end4 = 18

The iterator reaches end, push back(begin = 15, end = 18)

**Code:**

`class Solution {`

public:

vector<Interval> merge(vector<Interval>& intervals) {

if (intervals.size() == 0) return{};

vector<Interval> result;

Interval tmp;

map <int, int> mapping;

for (int i = 0; i < intervals.size();i++)

{

mapping[intervals[i].start] = INT_MIN;

}

for (int i = 0; i < intervals.size();i++)

{

mapping[intervals[i].start] = max(intervals[i].end, mapping[intervals[i].start]);

}

map<int, int>::iterator it = mapping.begin();

int begin = it->first, end = it->second;

for (it = mapping.begin(); it != mapping.end();it++)

{

if (it->first <= end)

{

end = max(it->second, end);

}

else

{

tmp = Interval(begin, end);

result.push_back(tmp);

begin = it->first;

end = it->second;

}

}

tmp = Interval(begin, end);

result.push_back(tmp);

return result;

}

};

**Timing:**

Timing is 12ms(beats 70%), the best is 9ms

The insert of map is O(logn)

The complexity of merging intervals is O(n)