then at that point we can just take the remaining intervals and then add them to the result and then we can return so those are a couple more of these simple cases right where we would not have to merge suppose we had an interval such as this one though right let's say NUMBER_TOKEN to NUMBER_TOKEN or something like that okay we we iterate through the first interval we see okay this interval is overlapping with this one how do we know if they're overlapping or not well we would check okay does the end value of the new interval is it less than the start value of this interval it's not okay is the start value of the new interval greater than the end value of the current interval it's not so if that if neither of those are the case that means this interval does not go after this interval and it does not go before this interval so that must mean that they are overlapping in which case we're going to merge them how are we going to merge them we're going to take the minimum of the left and the maximum of the right and then merge them together so when we merge them we're going to get a new interval such as this one zero two three and once we have this merged interval we're not going to actually add it to the output just yet because we know that this this interval could actually overlap with some other intervals that we now have that come following right and that's exactly the case it's overlapping with this other interval three four so we we've gotten rid of this first interval now we're going to be iterating to the second interval we're gonna see three four okay is this overlapping with our zero three interval yes it is so we're going to merge these as well we're gonna take the minimum of the left it's gonna be zero and the maximum of the right it's gonna be four so we merge these together so now we're gonna have a new interval uh from zero to NUMBER_TOKEN and we're still not going to add this to the output yet because it could technically still be overlapping with some following intervals in this case we're going to get to the third interval and in this case they're not overlapping how do we know that because the end value of this one NUMBER_TOKEN is less than the start value of the interval that we're at so what are we going to do we're going to take this the first interval add it to the result now and then we're going to take this interval add it to the result after it and then we're going to go to the next interval see that we don't have any more intervals remaining and then we're done so this is going to be our result in this case NUMBER_TOKEN NUMBER_TOKEN and NUMBER_TOKEN NUMBER_TOKEN our new intervals after we've merged them and they're in ascending order so that's kind of the general algorithm as you can see since it's already sorted we'll just have to iterate through the entire list of intervals once so the overall time complexity is going to be big o of n that's also going to be the memory complexity if you count the memory that we're going to use to create the result array with that being said we can hop into the code now but before i do let me just give you a very quick word from our sponsor for today if you want to get hired at top tech companies like google facebook and amazon then you need to check out interviewing dot io you'll practice realistic
START_SPONSOR_TOKEN today if you want to get hired at top tech companies like google facebook and amazon then you need to check out interviewing dot io you'll practice realistic END_SPONSOR_TOKEN