A solution to LeetCode Problem 56. Merge Intervals in JavaScript
In this problem, we are given an array of intervals, where each interval is an object with a start and end property. The intervals are not necessarily sorted. Our task is to merge any overlapping intervals and return the resulting array of intervals.
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.
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.
Constraints:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
Solution
To solve this problem, you can use a greedy approach, where you first sort the intervals based on the start time, and then you can merge the overlapping intervals one by one. Here is a JavaScript solution that demonstrates this approach:
function merge(intervals) {
if (!intervals.length) return intervals;
// sort intervals by start time
intervals.sort((a, b) => a[0] - b[0]);
// initialize the merged intervals with the first interval
let merged = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
let currentInterval = intervals[i];
let lastMergedInterval = merged[merged.length - 1];
// if the current interval overlaps with the last merged interval, merge them
if (currentInterval[0] <= lastMergedInterval[1]) {
lastMergedInterval[1] = Math.max(lastMergedInterval[1], currentInterval[1]);
} else {
// otherwise, add the current interval to the merged intervals
merged.push(currentInterval);
}
}
return merged;
}
This solution has a time complexity of O(n * log(n)), since the intervals are sorted using the built-in Array.sort() function, which has a time complexity of O(n * log(n)). The space complexity is O(n), since we create a new array to store the merged intervals.
I hope this helps! Let me know if you have any questions or suggestions for improvement.