# Leetcode Merge Intervals problem solution

Apr 6, 2023

In the Leetcode Merge Intervals problem solution 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

## Solution in C Programming

``````int resIdx;
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){

int i,j,k;
int val,s;
int min, max;
int **res;
resIdx=0;
for (i=0; i < intervalsSize; i++)
{
val = intervals[i][0];
k=-1;
for (j=i+1; j < intervalsSize; j++)
{
if (val > intervals[j][0])
{
val = intervals[j][0];
k = j;
}
}

if (k != -1)
{
s =  intervals[i][0];
intervals[i][0] = intervals[k][0];
intervals[k][0] = s;
s = intervals[i][1];
intervals[i][1] = intervals[k][1];
intervals[k][1] = s;
}
}
res = (int **)malloc(sizeof(int *) * intervalsSize);
for (i=0; i < intervalsSize; i++)
{
res[i] = (int *)malloc(sizeof(int) * 2);
}
*returnColumnSizes = (int *)malloc(sizeof(int) * intervalsSize);

min = intervals[0][0];
max = intervals[0][1];
for (i=1; i < intervalsSize; i++)
{
if (max < intervals[i][0] &&  max < intervals[i][1])
{
res[resIdx][0] = min;
res[resIdx][1] = max;
returnColumnSizes[0][resIdx] = 2;
resIdx++;
min = intervals[i][0];
max = intervals[i][1];

}
else if (max < intervals[i][1])
{
max = intervals[i][1];
}

}
res[resIdx][0] = min;
res[resIdx][1] = max;
returnColumnSizes[0][resIdx] = 2;
*returnSize = resIdx+1;

return &res[0];

}``````

## Solution in C++ Programming

``````class Solution {
public:
bool overlap(vector<int>& interval1, vector<int>& interval2)
{
return interval1[1] >= interval2[0];
}

vector<int> merge(vector<int>& interval1, vector<int>& interval2)
{
return {min(interval1[0], interval2[0]), max(interval1[1], interval2[1])};
}

vector<vector<int>> merge(vector<vector<int>>& intervals)
{
vector<vector<int>> res;
if(intervals.size() == 0)
return res;

sort(intervals.begin(), intervals.end(), [&](vector<int>& a, vector<int>& b){return a[0] < b[0];});
res.push_back(intervals[0]);
for(int i = 0; i < intervals.size(); i++)
{
if(overlap(res.back(), intervals[i]))
{
vector<int> tmp = merge(res.back(), intervals[i]);
while(!res.empty() && overlap(res.back(), tmp))
res.pop_back();
res.push_back(tmp);
}
else
res.push_back(intervals[i]);
}
return res;
}
};``````

## Solution in Java Programming

``````class Solution {
public int[][] merge(int[][] intervals) {
if (intervals == null || intervals.length == 0) return new int[0][0];

Arrays.sort(intervals, (a, b) -> {
return a[0] - b[0];
});

List<int[]> list = new ArrayList<>();

for (int i = 1; i < intervals.length; i++) {
int[] listInterval = list.remove(list.size() - 1);
int[] currInterval = intervals[i];
if (listInterval[1] >= currInterval[0]) {
listInterval[1] = Math.max(currInterval[1], listInterval[1]);
} else {
}
}

int[][] res = new int[list.size()][2];
for (int i = 0; i < res.length; i++)  res[i] = list.get(i);
return res;
}
}``````

## Solution in Python Programming

``````class Solution:
def merge(self, intervals):
intervals.sort()
result=[intervals[0]]
for i in range(1, len(intervals)):
if result[-1][1]<intervals[i][0]:
result.append(intervals[i])
else:
result[-1][1]=max(result[-1][1], intervals[i][1])
return result``````

## Solution in C# Programming

``````public class Solution {
public int[][] Merge(int[][] intervals) {
int r=1;
intervals = intervals.OrderBy(x => x[0]).ToArray();
//Array.Sort(intervals,(a, b) => {return a[0]-b[0];});
int start=intervals[0][0];
int end=intervals[0][1];

var res=new List<int[]>();

while(r<intervals.Length)
{
if(intervals[r][0]>end)
{
start=intervals[r][0];
end=intervals[r][1];
}
else if(intervals[r][0]<=end && intervals[r][1]>=end)
{
end=intervals[r][1];
}
r++;
}
return res.ToArray();

}
}``````

#### By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.