Merge Overlapping Intervals | GeeksforGeeks

This video is contributed by Harshit Jain.

[BigBlueRabbit]

Thanks for this - I was able to implement the algorithm in SQL Server for merging time intervals held in tables. Works great and very efficient :-)

[myselfjatin]

the comparator method used in sort for the two approaches are opposite. For the first approach with a stack we are sorting the interval in the increasing order of the start time. For the second approach for the interval we are sorting the interval in decreasing order of the starting time.

[xsuritox]

for the O(1) space complexity method, 1st step of algorithm should be sort array intervals in increasing order of starting time and NOT decreasing order of starting time, as shown on the video.

[dinakarmaurya]

without extra space algo can be more explained by taking example of inputs at the end of video!

[jamesqiu]

how can you afford to sort them first ? if the input is over 10Mil in total, or the input is real time data from the internet ...

[gurmeetchawla]

i think the logic above has an issue when there are intervals like {2, 4}, {5, 7} It might merge them what do you think.

[bhargavsai]

would have been better if you would have traced it and explained

[TechCornerWithAjay]

Could do better. Take an array filled with zeros from min to max times.
When we encounter, interval [a, b] fill array[a] to array[b] with ones, do it for all intervals. At the end traverse array and print all continuous segments as intervals.