# 56. Merge Intervals
##### tags: *`Medium`*, *`Array`*, *`Sort`*
[Leetcode](https://leetcode.com/problems/merge-intervals/)
## 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].

### Constraints:
* 1 <= intervals.length <= 10^4^
* intervals[i].length == 2
* 0 <= starti <= endi <= 10^4^

## Thinking Process

## Solution
### Code (Python3)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(interval[1], merged[-1][1])
        return merged

### Code (C++)

### Explanation

### Complexity
- Time: $O(nlogn)$
- Space: $O(n)$

### Submission Comparison

---
[Return to index](https://hackmd.io/ZYZVf7aZRd--0Sq85V20NA?view)