# JSDevLife

JavaScript Solutions, Competitive programming in JavaScript, MCQ in JS

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