Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/merge-intervals
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] overlaps, 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.
Constraints:
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= starti <= endi <= 10^4
Explanation
Brute force
Brute force approach is to start from the first interval and compare it every other interval. If it overlaps with any other interval, remove that other interval and merge the other in the first interval.
We repeat these same steps for the remaining intervals after first. The time complexity of this approach is O(N^2).
Efficient solution: Sorting
An efficient way is to first sort the time intervals by start time. Once the intervals are sorted, we merge all intervals in linear time. If interval[i] overlaps with interval[i - 1], then we combine these two intervals. If not, we add this interval to final answer.
Let's check the algorithm below:
- sort the intervals array sort(intervals.begin(), intervals.end())
- initialize vector result
- loop for interval in intervals
- if result.empty() || result.back()[1] < interval[0]
- result.push_back({interval[0], interval[1]})
- else
- result.back()[1] = max(result.back()[1], interval[1])
- return result
C++ solution
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> result;
for(auto interval: intervals){
if(result.empty() || (result.back()[1] < interval[0])){
result.push_back({interval[0], interval[1]});
} else {
result.back()[1] = max(result.back()[1], interval[1]);
}
}
return result;
}
};
Golang solution
func merge(intervals [][]int) [][]int {
result := [][]int{}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
for i, interval := range intervals {
if i == 0 {
result = append(result, interval)
continue
}
lastInterval := result[len(result) - 1]
if lastInterval[1] < interval[0] {
result = append(result, interval)
} else if interval[1] > lastInterval[1] {
lastInterval[1] = interval[1]
}
}
return result
}
Javascript solution
var merge = function(intervals) {
intervals.sort((i, j) => {
return i[0] - j[0];
})
let result = [];
for(let i = 0; i < intervals.length; i++) {
if(i == 0) {
result.push(intervals[i]);
continue
}
let lastInterval = result[result.length - 1];
if(lastInterval[1] < intervals[i][0]) {
result.push(intervals[i]);
} else if (lastInterval[1] > intervals[i][0]) {
lastInterval[1] = intervals[i][1];
}
}
return result;
};
Let's dry-run our algorithm to see how the solution works.
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Step 1: sort(intervals.begin(), intervals.end())
- intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Step 2: vector<vector<int>> result
Step 3: loop for(auto interval: intervals)
interval = [1, 3]
- if result.empty() || (result.back()[1] < interval[0])
true // as result is empty array
- result.push_back({interval[0], interval[1]})
result = [[1, 3]]
Step 4: for(auto interval: intervals)
interval = [2, 6]
- if result.empty() || (result.back()[1] < interval[0])
false || (3 < 2)
false || false
false
- else
- result.back()[1] = max(result.back()[1], interval[1])
result.back()[1] = max(3, 6)
result.back()[1] = 6
result = [[1, 6]]
Step 5: for(auto interval: intervals)
interval = [8, 10]
- if result.empty() || (result.back()[1] < interval[0])
false || (6 < 8)
false || true
true
- result.push_back({interval[0], interval[1]})
result.push_back({8, 10})
result = [[1, 6], [8, 10]]
Step 6: for(auto interval: intervals)
interval = [15, 18]
- if result.empty() || (result.back()[1] < interval[0])
false || (10 < 15)
false || true
true
- result.push_back({interval[0], interval[1]})
result.push_back({15, 18})
result = [[1, 6], [8, 10], [15, 18]]
Step 7: loop ends
Step 9: return result
So we return the result as [[1, 6], [8, 10], [15, 18]].
Top comments (0)