Merge Intervals
Problem Description
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Example 3:
Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.
Constraints:
- 1 <= intervals.length <= 104
- intervals[i].length == 2
- 0 <= starti <= endi <= 104
Solve it on LeetCode
Approaches
1. Brute Force - Comparing All Intervals
Intuition:
The simplest, although not the most efficient, way to solve the problem is to compare each interval with every other interval to check for any overlapping. If two intervals overlap, they are merged into one. This process continues until we can no longer find any new intervals to merge, indicating all possible merges have been completed.
Steps:
- Iterate over every interval and check with all other intervals whether they overlap.
- If two intervals overlap, merge them and replace in the original list.
- Continue this until no more merges can occur.
Code:
- Time Complexity: O(n^2), where n is the number of intervals. Each interval can potentially be compared with every other interval.
- Space Complexity: O(n), used for storing the merged intervals.
2. Sort and Merge
Intuition:
A more optimal way to tackle the problem is to take advantage of sorting. By sorting intervals based on the start time, we can efficiently check for overlaps by comparing each interval with the last interval in a merged list. If they overlap, merge them; otherwise, just add the interval to the merged list.
Steps:
- Sort the list of intervals based on the starting time.
- Iterate through sorted intervals.
- Compare the current interval with the last merged interval:
- If they overlap, merge them.
- If not, simply add the current interval to the result.
Code:
- Time Complexity: O(n log n), where n is the number of intervals. Sorting the intervals dominates the time complexity.
- Space Complexity: O(n), used for storing the merged intervals.