This is our solution and implementation to problem #56: Merge Intervals on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Merge Intervals on LeetCode.
Problem Analysis
Given a list of intervals, we need to return a list that merges all intervals that intersect in the original list. The output must be non-overlapping intervals. We want to avoid quadratic iteration (loop inside of a loop). Note that if we sort the input by order of increasing start (i.e. sort by interval[0]), we can figure out which intervals are intersecting using only one iteration through the input. For each interval, if its start value is inbetween the previous start value and maximum end value found so far, it belongs to the same interval.
Implementation Strategy
We will initially allocate an arraylist mergedIntervals to store combined intervals as we find them. Then, we will sort the input array and create new variables minLeft and maxRight to keep track of the merged interval as we go. We will initially set them to the start and end of the first interval. Then, for each interval starting with the 2nd (i=1):
- Set variables left and right to the values in intervals[i].
- If the left intersects: left >= minLeft && left <= maxRight, set maxRight to the max value of right and maxRight.
- If not:
- Add [minLeft,maxRight] to mergedIntervals
- Set minLeft and maxRight to values left and right.
That last step sets-up the remaining iteration for this next non-overlapping interval. When the loop is concluded, you need to add the last interval to mergedIntervals before returning.
Space and Time Complexity
The time complexity is O(n log n) because we spend some initial time sorting, then iterate through the values exactly one. The space complexity is O(n) because we need to store the output intervals.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.