# [LC] 56. Merge Intervals

TechGiven an array of `intervals`

where `intervals[i] = [start`

, merge all overlapping intervals, and return _{i}, end_{i}]*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 <= 10`

^{4}`intervals[i].length == 2`

`0 <= start`

_{i}<= end_{i}<= 10^{4}

Approach

Sort by 1st element, then check if the next interval is overlapped. If the checking interval’s 1st element is more than the current end time, then change the checking interval to the current interval.

```
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
rslt = []
if len(intervals) == 0:
return rslt
intervals.sort()
start_x, start_y = intervals[0]
for i in range(1, len(intervals)):
if start_y < intervals[i][0]:
rslt.append([start_x, start_y])
start_x, start_y = intervals[i]
elif start_y < intervals[i][1]:
start_y = intervals[i][1]
rslt.append([start_x, start_y])
return rslt
```

Time Complexity: O(NlogN)

Space Complexity: O(1)

Optimization: maybe we can use the heap?

**Submission**

Runtime: 92 ms, faster than 35.73% of Python3 online submissions for Merge Intervals.

Memory Usage: 16.3 MB, less than 12.13% of Python3 online submissions for Merge Intervals.