1. Problem Statement (Simple Explanation)
You’re given an array of intervals: intervals[i] = [start_i, end_i]
You must:
Merge all overlapping intervals.
Return the resulting list of non-overlapping intervals that cover all intervals in the input.
Two intervals [a,b] and [c,d] overlap if: c <= b (i.e., start of the next is ≤ end of the current)
Note: intervals touching at a point (like [1,4] and [4,5]) are considered overlapping and should be merged.
2. Examples
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
[1,3] and [2,6] overlap → merge to [1,6].
[8,10] and [15,18] do not overlap with others.
Output: [[1,6],[8,10],[15,18]]
Example 2:
Input: intervals = [[1,4],[4,5]]
[1,4] and [4,5] overlap (end of first equals start of second) → merge to [1,5].
Output: [[1,5]]
Example 3:
Input: intervals = [[4,7],[1,4]]
After sorting → [[1,4], [4,7]], which overlap → [1,7].
Output: [[1,7]]
3. Approach – Sort + One Pass Merge
Idea:
Sort intervals by start time.
Initialize merged as an empty list.
Iterate through the sorted intervals:
If merged is empty, or if the current interval does not overlap with the last one in merged:
Append the current interval to merged.
Else (they do overlap):
Merge by updating the end of the last interval in merged.
merged_last_end = max(merged_last_end, current_end)
Overlap condition:
Let last = merged[-1] and curr be the current interval.
They overlap if: curr.start <= last.end
Pseudo-code:
Let n = intervals.length:
Sorting: O(nlogn)
Single pass merge: O(n)
Total time: O(nlogn)
Space: O(n) for output; extra overhead is O(1) or O(n) depending on implementation.
4. Java code
6. C++ code
Comments
Post a Comment