leetcode-56

56. Merge Intervals

Leetcode 56

I solved this problem using C++.
My idea: sort the intervals by their first element, then merge the intervals.

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
class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {
            return a[0] < b[0];
        });
        vector<vector<int>> merged;
        vector<int> currentInterval = intervals[0];
        for (int i = 1; i < intervals.size(); i++)
        {
            if (currentInterval[1] >= intervals[i][0] && currentInterval[0] <= intervals[i][1])
            {
                currentInterval[0] = min(currentInterval[0], intervals[i][0]);
                currentInterval[1] = max(currentInterval[1], intervals[i][1]);
            }
            else
            {
                merged.push_back(currentInterval);
                currentInterval = intervals[i];
            }
        }
        merged.push_back(currentInterval);
        return merged;
    }
};

It’s like recursive merge sort.
Merge current interval as new current interval, the next interval is same as the current interval.
If the next interval is not overlapping with the current interval, push the current interval to the merged intervals and set the next interval as the new current interval.
Finally, push the last current interval to the merged intervals.

e.g.
intervals = [[2,3],[4,5],[6,7],[8,9],[1,10]]
sort intervals = [[1,10],[2,3],[4,5],[6,7],[8,9]]
merged = []
currentInterval = [1,10]

if currentInterval[1] >= intervals[1][0] && currentInterval[0] <= intervals[1][1]:
update currentInterval with new up and down bound

e.g.
intervals = [[1,3],[2,6],[8,10],[15,18]]
sort intervals = [[1,3],[2,6],[8,10],[15,18]]
merged = []
currentInterval = [1,3]

from [1, 3] to [2, 6]:
currentInterval => [1, 6]
[8, 10] is not overlapping with [1, 6], so push [1, 6] to merged intervals
now currentInterval = [8, 10]
…
finally push the last currentInterval to merged intervals

conclusion

It’s a simple problem…