> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/greedy/medium/56.-merge-intervals.md).

# 56. Merge Intervals

## Problem Statement

<br>

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*.

&#x20;

**Example 1:**

<pre><code><strong>Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
</strong><strong>Output: [[1,6],[8,10],[15,18]]
</strong><strong>Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: intervals = [[1,4],[4,5]]
</strong><strong>Output: [[1,5]]
</strong><strong>Explanation: Intervals [1,4] and [4,5] are considered overlapping.
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= intervals.length <= 104`
* `intervals[i].length == 2`
* `0 <= starti <= endi <= 104`

## Intuition

```
Approach:

Merge the intervals as we go along, sort based on start value
Then modify the array

Edge case:
1,5  : 2,4
We take max of 5,4 when we modify end time
```

### Links

<https://leetcode.com/problems/merge-intervals/description/>

### Video Links

<https://www.youtube.com/watch?v=44H3cEC2fFM&ab_channel=NeetCode>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        vector<vector<int>> ans;
        sort(intervals.begin(), intervals.end());
        ans.push_back(intervals[0]);

        for(int i=1; i<n; i++){
            int size = ans.size();
            if( intervals[i][0] <= ans[size-1][1] ){
                ans[size-1][1] = max(ans[size-1][1], intervals[i][1]);
                //1,5 : 2,4 To account this we take max
            }
            else{
                ans.push_back(intervals[i]);
            }
        }

        return ans;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###