JavaScript Algorithms: Merge intervals (LeetCode)

Photo by Maxim Melnikov on Unsplash

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] 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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Solution

In this problem, we can sort the intervals in advance and after that we can go through the sorted array and try to merge somehow these intervals. The key thing here is to come up with how we can merge the intervals.

An idea is pretty simple. We need to check if the current interval begins after the previous interval ends. We can easily check it because we’ve sorted the intervals.

The time complexity is O(nlogn) because of the sort, and space complexity is O(n) because we use result to store merged intervals.

I hope, it was useful for you. Thanks for reading! Looking forward to your feedback. See you soon ✌️