class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // Brute Force Solution Time O(N^2) & Auxiliary Space O(1)
        int len=intervals.size();
        if(len<=1)
            return intervals;
        sort(intervals.begin(),intervals.end()); // Time taken by sort() is O(NlogN)
        vector<vector<int>> res;
        for(int i=0;i<len;i++){
            int a=intervals[i][0];
            int b=intervals[i][1];
            // for loop inside for loop takes time of O(N^2)
            for(int j=i+1;j<len;j++){
                int c=intervals[j][0];
                int d=intervals[j][1];
                if(b>=c){ 
                    // Comparing pairs : (a,b) & (c,d)
                    // Interval overlap condition example - a=3,b=7,c=5,d=9
                    //  Real Line---a(3)------c(5)******b(7)-------d(9)----
                    // (a,max(b,d)) should be inserted in result(res) vector.
                    // b will only get updated if there is an overlap 
                    // so as to merge maximum number of intervals
                    b=max(b,d);
                    // i pointer should now point to the pair pointed by j 
                    // and in next iteration of j loop, j will point to the 
                    // pair next to the one pointed by this i
                    i=j;
                }
            } 
            res.push_back({a,b});
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // Optimal Solution Time O(NlogN) & Auxiliary Space O(1)
        int len=intervals.size();
        if(len<=1)
            return intervals;
        sort(intervals.begin(),intervals.end());
        vector<vector<int>> res; // result vector
        // insert the first element into the result vector
        res.push_back(intervals[0]);
        for(int i=1;i<len;i++){
            if(res.back()[1]>=intervals[i][0])
                // back() points to the final element of the vector.
                // Update the endpoint of final element of result 
                // vector if there is an overlap with intervals[i]
                res.back()[1]=max(res.back()[1], intervals[i][1]);
            else
                // If no overlap, insert intervals[i]
                res.push_back(intervals[i]);
        }
        return res;
    }
};