{"id":10013,"date":"2022-09-27T10:09:58","date_gmt":"2022-09-27T10:09:58","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=10013"},"modified":"2022-10-10T09:27:32","modified_gmt":"2022-10-10T09:27:32","slug":"merge-overlapping-intervals","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/merge-overlapping-intervals\/","title":{"rendered":"Merge Overlapping Intervals"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement<\/h3>\n

You will be given an array<\/a> of time intervals that will be in any random order. You have to merge all the overlapping intervals and print only the mutually exclusive intervals i.e. the non-overlapping intervals.<\/p>\n

Example<\/h3>\n

Consider the example shown below.<\/p>\n

\"\"<\/p>\n

So, in the above example, {10,30} overlaps with {20,40} since the starting time of interval {20,40} i.e. 20 is not greater than the end time of the interval {10,30}. Hence, we merge them to form the interval {10,40}. <\/p>\n

Merge Overlapping Intervals Brute Force Approach<\/h3>\n

Let us first understand the brute force approach for merging the overlapping intervals. It is straightforward. We will take each interval once and compare it with all the other intervals. If it overlaps with some interval, we merge them. So, in this approach, we are taking an interval out of N intervals and comparing it with the rest N-1 intervals. In the worst case, we will have to do this for all N intervals (no overlapping intervals exist in the worst case). So, the time complexity will be O(N2). Hence, we will not implement (code) this approach. Let us think of something better.<\/p>\n

Merge Overlapping Intervals Using Stack<\/h3>\n

Consider the following intervals shown below.<\/p>\n

\"\"<\/p>\n

So, let us try to merge the overlapping intervals in this array. First of all, we will sort the array based on increasing the order of start time as shown below.<\/p>\n

\"\"<\/p>\n

Now, we will take an empty stack and push the first interval within the stack.<\/p>\n

\"\"
\nNow, the next interval is 5-12. Since the start time of the next interval i.e. 5 is less than the end time of the interval present at the top of the stack, this means that these intervals are overlapping. Hence, we have to merge them.<\/p>\n

So, we compare the intervals and find out that the end time of the second interval i.e. 12 is greater than the end time of the interval present at the top of the stack. So, we will change the end time of the interval present at the top of the stack to 12 and hence the intervals are merged.<\/p>\n

\"\"<\/p>\n

Now, we move to the next interval i.e. 14-19. Here, the start of this interval is greater than the end of the interval present at the top of the stack. So, they are non-overlapping and we will simply add 14-19 to the top of the stack.<\/p>\n

\"\"<\/p>\n

We added 14-19 to the top of the stack because we are sure that no interval now will merge with intervals 1-12. This is because the intervals have been sorted concerning their start times and if the start time of the interval 14-19 is not less than the end time of 1-12, the further intervals will have a start time greater than 14 and will not merge with 1-12.<\/p>\n

So, the next interval is 22-28. The start time of this interval is also greater than the end time of the interval present at the top of the stack i.e. 22 is greater than 19. So, these are non-overlapping intervals and we will add 22-28 to the top of the stack now.<\/p>\n

\"\"<\/p>\n

Next, we have the intervals 25-27. This interval has a start time less than the end time of the interval present at the top of the stack i.e. 25 is less than 28. So, these intervals are overlapping and we will have to merge them.<\/p>\n

This time, the end time of the interval at the top of the stack i.e. 28 is greater than the end time of the current interval i.e. 27. So, the current interval will be merged with the top of the stack interval, and will completely be overlapped by the interval at the top of the stack i.e. the end time of the top of the stack will not change as 25-27 lies completely inside 22-28.<\/p>\n

\"\"<\/p>\n

Now, the last interval 27-30 is considered. This interval has a start time less than the end time of the interval at the top of the stack. So, merging will take place here as well.<\/p>\n

\"\"<\/p>\n

So, the reverse order of the intervals now presents in the stack are non-overlapping intervals in sorted order.<\/p>\n

\"\"<\/p>\n

So, this is how we can solve this problem in an optimized approach using Stack and sorting. Now that we have understood this approach, let us write the code for the same.<\/p>\n

,Code Implementation<\/h3>\n\t\t\t\t\t\t