Problem Description

Medium

Array, Sorting

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: Sorting + Simple Iteration

The trick with this problem is realizing that if we go in sorted order of start values, the only thing we need to check is if end ≥ other_start. It is guaranteed that if we start from the beginning and merge in this order, we will get contiguous runs of merges. I was confusing myself with the example of if the first element in the list has a very large end, but if we just take the max of the values when we merge, everything after will get folded into this first element.

Next, we just need to maintain a result array that builds these continuous runs. We can do some clever programming to “merge” these lists as we go, and append to the result list once our continuous run ends.

The code is elegantly simple once you realize a few clever tricks that you can do.

Code