## Sunday, April 7, 2013

### [LeetCode] Merge Intervals, Solution

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]`.
» Solve this problem

[Thoughts]

[Code]

``````1:       vector<Interval> merge(vector<Interval> &intervals) {
2:            vector<Interval> result;
3:            for(int i =0; i< intervals.size(); i++)
4:            {
5:                 insert(result, intervals[i]);
6:            }
7:            return result;
8:       }
9:       void insert(vector<Interval> &intervals, Interval newInterval) {
10:            vector<Interval>::iterator it = intervals.begin();
11:            while(it!= intervals.end())
12:            {
13:                 if(newInterval.end<it->start)
14:                 {
15:                      intervals.insert(it, newInterval);
16:                      return;
17:                 }
18:                 else if(newInterval.start > it->end)
19:                 {
20:                      it++;
21:                      continue;
22:                 }
23:                 else
24:                 {
25:                      newInterval.start = min(newInterval.start, it->start);
26:                      newInterval.end = max(newInterval.end, it->end);
27:                      it =intervals.erase(it);
28:                 }
29:            }
30:            intervals.insert(intervals.end(), newInterval);
31:       }
``````