Merge Intervals
Medium
Array
Sorting
Intervals
Given an array of `intervals` where `intervals[i] = [startᵢ, endᵢ]`, 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]]
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]

Constraints

  • •1 <= intervals.length <= 10⁴
  • •intervals[i].length == 2
  • •0 <= startᵢ <= endᵢ <= 10⁴
Time Complexity
O(n log n)
Space Complexity
O(n)
14
Case 1
Input: [[1,3],[2,6],[8,10],[15,18]]
Expected: [[1,6],[8,10],[15,18]]
Case 2
Input: [[1,4],[4,5]]
Expected: [[1,5]]
Case 3
Input: [[1,4],[2,3]]
Expected: [[1,4]]