# 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.

## No comments:

## Post a Comment