Merge interval pattern: Merge Overlapping Intervals

Problem Statement:

You are given an array of intervals arr[i] = [start_i, end_i].

You need to merge all overlapping intervals, so that the only mutually exclusive intervals are present.

Example

Input: arr[] = [[1, 3], [2, 4], [6, 8], [9, 11]]
Output: [[1, 4], [6, 8], [9, 10]]

Explanation: 

Only [1, 3], [2, 4] are overlapping, hence they are merged into [1, 4]

Solution 1: Sorting Approach

Sort the array based on the starting points.

Then iterate over each interval, if the current interval overlaps the last merged interval, then merge them both, else append the interval to the result.

Time Complexity: O(n*log(n))
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


vector<vector<int>> solution(vector<vector<int>>& arr) {

    // sort the array
    sort(arr.begin(), arr.end());
  
    vector<vector<int>> res;

    res.push_back(arr[0]);

    for (int i = 1; i < arr.size(); i++) {
        vector<int>& last = res.back();
        vector<int>& curr = arr[i];

        if (curr[0] <= last[1]) 
            last[1] = max(last[1], curr[1]);
        else 
            res.push_back(curr);
    }

    return res;
}

int main() {

    vector<vector<int>> arr = {{1, 3}, {2, 4}, {6, 8}, {9, 11}};
    vector<vector<int>> res = solution(arr);

  	for (vector<int>& interval: res) 
        cout << interval[0] << " " << interval[1] << endl;
 
    return 0;
}

Output

1 4
6 8
9 11