# LC 56. Merge Intervals

### [Problem link](https://leetcode.com/problems/merge-intervals/)

###### tags: `leedcode` `python` `c++` `medium` `Greedy`

Given an arrayof <code>intervals</code>where <code>intervals[i] = [start_i, end_i]</code>, 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:**

- <code>1 <= intervals.length <= 10⁴</code>
- <code>intervals[i].length == 2</code>
- <code>0 <= start_i <= end_i <= 10⁴</code>

## Solution 1 - Greedy
#### Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])

        res = [intervals[0]]

        for i in range(1, len(intervals)):
            left, right = res[-1]
            if right >= intervals[i][0]:
                res[-1][1] = max(right, intervals[i][1])
            else:
                res.append(intervals[i])

        return res

#### C++

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[0] < b[0];
    }

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);

        vector<vector<int>> res;
        int left = intervals[0][0];
        int right = intervals[0][1];
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] <= right) {
                right = max(right, intervals[i][1]);
            } else {
                vector<int> tmp = {left, right};
                res.push_back(tmp);
                left = intervals[i][0];
                right = intervals[i][1];
            }
        }
        vector<int> tmp = {left, right};
        res.push_back(tmp);
        return res;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| -------------------- | --------------- | ---------------- |
>| Solution 1 (python) | O(nlogn) | O(n) |
>| Solution 1 (c++) | O(nlogn) | O(logn) |

## Note
sol1:
c++ space complexity: O(logn) for sort algo.