Merge Overlapping Intervals | Brute, Optimal with Precise TC analysis

We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.

You can follow me across social media, all my handles are below:

0:00 Introduction of Course
00:41 Problem Statement
01:15 Overlapping example
03:27 Brute force
03:56 approach
09:39 Code
13:30 Complexity
16:22 Optimal approach
16:38 Intuition
18:55 Code
21:36 Complexity

[takeUforward]

Do give us a like if you understood everything, it won't cost you much :)

[Akash-yrif]

This is the first question where I took 1hr to understand the Brute force & 10 min to understand the Optimal logic 🙂

[darshanrokkad]

understanding of brute force took me more time than understanding of optimal

[badass_yt]

I generally do not comment even on good videos, but after watching this video, i really wanna say amazing explanation. You made a difficult problem easy. Excellent clarity of concept. Striver, you are the best💯

[NithinvKumar-ukhe]

One of the greatest free course that I ever seen in YouTube

[iWontFakeIt]

I think my code is more intuitive (atleast to me) rather than the code you shown.(both approaches are same) (also I am not complaining, I am sharing this so that others can also share their opinion on mine). Below is my code:

#include <bits/stdc++.h>
/*

intervals[i][0] = start point of i'th interval
intervals[i][1] = finish point of i'th interval

*/

vector<vector<int>> &intervals)
{
int n = intervals.size();
sort(begin(intervals), end(intervals));
vector<vector<int>> ans;
int i = 1;
int start = intervals[0][0], end = intervals[0][1];
while(i<n){
int new_start = intervals[i][0], new_end = intervals[i][1];
if(new_start <= end){
end = max(end, new_end);
}else{
vector<int> temp;
temp.push_back(start);
temp.push_back(end);
ans.push_back(temp);
start = new_start;
end = new_end;
}
i++;
}
vector<int> temp;
temp.push_back(start);
temp.push_back(end);
ans.push_back(temp);
return ans;
}

[sasanklakimsetti]

Understood very well. Thought that the problem would be extremely tough by looking at the question. But he proved me wrong with his explanation.

[anshikavlogs]

you make this question so easy to be understood by your proper explanation .🔥🔥 really thanks a lot

[syedFAHIM-elwr]

By Liking, We also tell you tube algorithm that provide us with such content instead of distracting useless videos!!!

When i understood this, I started liking every quality content videos and my recommendation is now really good.

Understood!

I was able to build up the logic but could not code it by myself...
Waiting for that magic to happen when i can code even listening to music

[mehulthuletiya]

00:41 Problem Statement
01:15 Overlapping example
03:27 Brute force
03:56 approach
09:39 Code
13:30 Complexity
16:22 Optimal approach
16:38 Intuition
18:55 Code
21:36 Complexity

[deathigniter]

i am glad i was able to think of optimal solution directly and didnt even realised it was optimal. Felt like
Brute Force was more tougher than the optimal one. LOL

[shubhamagarwal]

#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India..

[wanderer_ankur]

Man i have always been scared of arrays especially but after going through this sheet gradually my confidence is increasing. This is such a good resource for learning DSA. Thanks a lot striver bro for making this :)

[jatinukey]

The approaches you have taught in this video, 60-70% both the approaches come in my mind but i was struggling to implement it. Thank you very much bhaiya for this video! You are always a great tutor for me and everyone ❤❤

[Braveuser-xj]

when I see your video i thought why we don't get this type of teacher in our engineering college .... i think 1.5 st years is enough to crack any coding interview

[aryanthapa]

was watching this tutorial on your website before after watching the video I came here to just like and comment on this video to tell how beautiful the explanation was loved it striver bhaiya❤❤

[notcountdankula]

Python Code 🐍

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:

ans = []

intervals.sort()

ans.append(intervals[0])

for i in intervals:
start = i[0]
end = i[1]

if start <= ans[-1][1]:
ans[-1][1] = max(end, ans[-1][1])
else:
ans.append(i)

return ans

[artifice_abhi]

A little change in the code (although striver's code is shorter) by updating the end every time we move to the next index:
vector<vector<int>> intervals) {
// Code here
sort(intervals.begin(), intervals.end());

vector<vector<int>> ans;

int start = intervals[0][0];
int end = intervals[0][1];

for(int i = 1; i<intervals.size() ; i++){
if(intervals[i][0] <= end) end = max(end, intervals[i][1]);
else{
ans.push_back({start, end});

start = intervals[i][0];
end = intervals[i][1];
}
}
ans.push_back({start, end});

return ans;

}

[alphaCont]

we can do it O(1) also in space, by checking the next element if it is overlapped we just change the current elements [1] element with max, than we just remove the [i+1] from the array and in the end we will have just our answer

[ritikrajsinha]

bhaiya u re inspiration to all thrown ones like us thank u get a lot hope from u