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<>();
list.add(intervals[0]);
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]);
list.add(listInterval);
} else {
list.add(listInterval);
list.add(currInterval);
}
}
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 resultSolution 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)
{
res.Add(new int[2]{start, end});
start=intervals[r][0];
end=intervals[r][1];
}
else if(intervals[r][0]<=end && intervals[r][1]>=end)
{
end=intervals[r][1];
}
r++;
}
res.Add(new int[2]{start, end});
return res.ToArray();
}
}Also read,