56. Merge Intervals

The problem is not stating very clearly. It should say that the output of the array is sorted in ascending order. With this assumption, the problem becomes clear:

First of all, we need to sort the array according to the start point.

Then, scan the array and push the interval to the result if intervals[i].start > res.back().end, i.e. no overlay. Otherwise, update the last interval in the result, i.e. res.back().

1:  /**  
2:   * Definition for an interval.  
3:   * struct Interval {  
4:   *   int start;  
5:   *   int end;  
6:   *   Interval() : start(0), end(0) {}  
7:   *   Interval(int s, int e) : start(s), end(e) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<Interval> merge(vector<Interval>& intervals) {  
13:      vector<Interval> res;  
14:      if (intervals.size() == 0) return res;  
15:      sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) { return a.start < b.start; });  
16:      res.push_back(intervals[0]);  
17:      for (int i = 1; i < intervals.size(); i++) {  
18:        if (intervals[i].start > res.back().end) res.push_back(intervals[i]);  
19:        else {  
20:          res.back().end = max(res.back().end, intervals[i].end);  
21:        }  
22:      }  
23:      return res;  
24:    }  
25:  };