56. Merge Intervals [Leetcode][C++]

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; } };