Problem description:

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution:

  1. First of all, we can sort the array of intervals by its start value. The sort can use lambda function.
  2. After we sort the array, we can easily found out that the only condition we need to check is whether if i‘s end value is smaller than i+1‘s start value.

For example:
original: [[4,3],[2,6],[3,5],[7,18]]
sorted: [[2,6],[3,5],[4,7],[8,18]]

  • init round: push the [2,6] into result.
  • 1st round:
    compare [2,6] and [3,5]. 6 is greater than 3, so we then compare end value from both range.
  • 2nd round:
    compare [2,6] and [4,7]. update [2,6] to [2,7]
  • 3rd round:
    compare [2,7] and [8,18]. Since 8 is greater than 7, it can not merge together, so we push [8,18] into the result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
    /*static bool comp(Interval a, Interval b){
        return a.start< b.start;
    }*/
    
    vector<Interval> merge(vector<Interval>& intervals) {
        if (intervals.empty()) return vector<Interval>{};
        vector<Interval> res;
        //sort(intervals.begin(), intervals.end(), comp);
        sort(ins.begin(), ins.end(), [](Interval a, Interval b){return a.start < b.start;});
        
        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (res.back().end < intervals[i].start) res.push_back(intervals[i]);
            else
                res.back().end = max(res.back().end, intervals[i].end);
        }
        return res;
    }
};

reference: