## Algorithm

Problem Name: 56. Merge Intervals

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] 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:

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

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int cmp(const void *a, const void *b) {
return (*(struct Interval *)a).start - (*(struct Interval *)b).start;
}
struct Interval* merge(struct Interval* intervals, int intervalsSize, int* returnSize) {
int i, j;

if (intervalsSize  < = 0) return NULL;

qsort(intervals, intervalsSize, sizeof(struct Interval), cmp);

i = 0;
for (j = 1; j  <  intervalsSize; j ++) {
if (intervals[j].start > intervals[i].end) {
// append
intervals[++ i] = intervals[j];
} else if (intervals[j].end > intervals[i].end) {
// merge
intervals[i].end = intervals[j].end;
}   // ignore it
}

*returnSize = i + 1;

return intervals;
}
``````
Copy The Code &

Input

cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

cmd
[[1,6],[8,10],[15,18]]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b){ return a.start < b.start; });
vector < Interval>res;
for(int i = 0; i  <  intervals.size(); i++)
if(res.empty() || res.back().end < intervals[i].start) res.push_back(intervals[i]);
else res.back().end = max(res.back().end, intervals[i].end>;
return res;
}
};
``````
Copy The Code &

Input

cmd
intervals = [[1,4],[4,5]]

Output

cmd
[[1,5]]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt((int[] o) -> o[0]).thenComparingInt(o -> o[1]));
List < int[]> mergedIntervals = new ArrayList<>();
int idx = 0;
while (idx  <  intervals.length) {
int currentStart = intervals[idx][0];
int currentEnd = intervals[idx][1];
idx++;
while (idx  <  intervals.length && intervals[idx][0] <= currentEnd) {
currentEnd = Math.max(intervals[idx][1], currentEnd);
idx++;
}
}
int[][] result = new int[mergedIntervals.size()][2];
for (int i = 0; i  <  mergedIntervals.size(); i++) {
result[i] = mergedIntervals.get(i);
}
return result;
}
}
``````
Copy The Code &

Input

cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

cmd
[[1,6],[8,10],[15,18]]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const merge = function(intervals) {
intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1])
const res = [intervals[0]]
for(let i = 1, n = intervals.length; i  <  n; i++) {
const [s, e] = intervals[i]
const pre = res[res.length - 1]
if(s <= pre[1]) {
pre[1] = Math.max(pre[1], e)
} else {
res.push(intervals[i]>
}
}
return res
};

``````
Copy The Code &

Input

cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

cmd
[[1,6],[8,10],[15,18]]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
res = []
intervals.sort(key = lambda x: x.end)
for intr in intervals:
if not re:
res.append([intr.start, intr.end])
else:
s = intr.start
while res and res[-1][1] >= intr.start:
s = min(s, res.pop()[0])
res.append([s, intr.end])
return res
``````
Copy The Code &

Input

cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

cmd
[[1,6],[8,10],[15,18]]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _056_MergeIntervals
{
public int[][] Merge(int[][] intervals)
{
if (intervals.Length  < = 1) return intervals;

Array.Sort(intervals, (a, b) =>
{
var comp = a[0].CompareTo(b[0]);
if (comp == 0)
comp = a[1].CompareTo(b[1]);
return comp;
});

var result = new List < int[]>();
for (int i = 1; i  <  intervals.Length; i++)
{
if (result.Last()[1] >= intervals[i][0])
{
if (result.Last()[1] < intervals[i][1])
result.Last()[1] = intervals[i][1];
}
else
}

return result.ToArray(); ;
}
}
}
``````
Copy The Code &

Input

cmd
intervals = [[1,3],[2,6],[8,10],[15,18]]

Output

cmd
[[1,6],[8,10],[15,18]]