Merge Intervals

Problem

Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

You may return the answer in any order.

Note: Intervals are non-overlapping if they have no common point. For example, [1, 2] and [3, 4] are non-overlapping, but [1, 2] and [2, 3] are overlapping.

Examples

Example 1:

Input: intervals = [[1,3],[1,5],[6,7]]

Output: [[1,5],[6,7]]

Example 2:

Input: intervals = [[1,2],[2,3]]

Output: [[1,3]]

Constraints

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• 0 <= start <= end <= 1000

You should aim for a solution as good or better than O(nlogn) time and O(n) space, where n is the size of the input array.

Solution

Sort the intervals based on start, then insert one at a time, checking if a merge needs to be done.

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // Sort intervals
        std::sort(intervals.begin(), intervals.end(), 
            [](const auto &lhs, const auto &rhs){
                return lhs[0] < rhs[0];
            });
        vector<vector<int>> result = {intervals[0]};
        // Scan forward, if end of previous interval overlaps with 
        //  start of current interval, merge
        for (int i = 1; i < intervals.size(); ++i) {
            if (result.back()[1] >= intervals[i][0]) {
                result.back()[1] = std::max(result.back()[1], intervals[i][1]);
            } else {
                result.push_back(std::move(intervals[i]));
            }
        }
        return result;
    }
};