All suggestions are welcome. Please upvote if you like it. Thank you.
Leetcode Problem Link: 56. Merge Intervals
Brute Force Solution:
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;
}
};
Efficient Solution:
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;
}
};
All suggestions are welcome. Please upvote if you like it. Thank you.
Top comments (0)