Hello and welcome back brave human being,

The problem we are going to solve today is easy when knowing the right tricks.

Which I’m about to teach you.

Day 10: 56. Merge intervals

Given a set of time intervals in any order, merge all overlapping intervals into one.

Naive solution:

The naive solution would be to do a double for loop and compare by first, comparing the first interval with the rest of the intervals, if it overlaps with any other interval, remove it and merge it into the first interval. This solution takes O(N²).

Can we make it better?

YES! 👏 

By sorting!! but any sort, a sort based on start time.

Why?

Sorting by start time will allow us to identify the overlapping intervals more easily.

Once sorted, push the first interval into a stack.

Iterate through the array and for each interval:

• If the current interval does not overlap with the top of the stack, push the interval to the stack.

• If the current interval does overlap with the top of the stack, update the stack top with the ending time of the current interval.

Once you are done iterating through all of the intervals, the stack will contain the merged intervals. This solution requires an O(N log N) time complexity and requires O(N) auxiliary memory.

Let’s dig in with an example:

Final Solution

Now, let’s add it to our LeetCode Tracker: