Leetcode: Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Example 1:
Input: [[2,6],[8,10],[15,18], [1,3]]
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.

Question Link: Merge Intervals

Solution: 

The brute force way to approach such a problem is select each interval and check from all the rests if it they can be combined?
If Yes, combine them, form the new interval and check again.
If No, put that interval in the result and continue.

But the above solution, have some problems:
1. It is actually difficult to implement.
2. It requires multiple recursions and graphs (read Connected Components).
3. This is not optimal [ O(N^2) Time Complexity ].

In conclusion, its better to further think about it.

Lets say if the intervals come in a partilar order, say sorted on the basis of first and then second values. Therefore, we know for each interval it can only combine with interval following it or previous to it and if possible we can combine intervals in a linear fashion.

Explaination

Firstly sort all the intervals based on firstly the left and then right pair values.

For each interval inteval[i] (a,b), select l and r as left and right hand of the interval:
Check if inteval[i+1] is can be combined to inteval[i].
If Yes, make r = max(r, interval[i+1].right) and continue with the current interval.
If No, save the current interval and continue to the next interval.

Now lets try to solve on the following example:
[[12,15], [12,17], [2,4], [16,18], [4,7], [9,11], [1,2]]

First step is to sort the intervals. After sorting we get:
[[1,2], [2,4], [4,7], [9,11], [12,15], [12,17], [16,18]]

Then:

Code

Implemented in C++.
First we need to write a comparator to help sort intervals in vectors format. We wouldn’t require this if the intevals were given in pairs format.

static bool comp(const vector<int> a,const vector<int> b){
    if(a[0]==b[0]) return a[1]<b[1];
    else return a[0]<b[0];
}

Main code to implement the logic:

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return intervals; // if zero size
        sort(intervals.begin(), intervals.end(), comp); //sorting using custom comparator
        vector<vector<int>> ans; //for saving result
        int l=0,r=INT_MIN; // initial parameters
        for(int i=0;i<intervals.size();i++){
            if(intervals[i][0]<=r){ // if intervals can be merged
                r = max(r, intervals[i][1]);
            }
            else{ // if intervals can't be merged
                if(i>0)ans.push_back(vector<int>{l,r}); //saving the result
                l=intervals[i][0]; r=intervals[i][1];
            }
        }
        ans.push_back(vector<int>{l,r});
        return ans;
    }

The time complexity of this solution will be:
1. Sort the intervals: O( N logN ).
2. Merge Logic is based on Two pointer technique. Each interval is selected only once: so O( N ).

The final time complexity will be O( N logN ).