Merge Intervals Problem: 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 :
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].
Table of Contents
Merge Intervals Problem Solution
Problem Solution In Python
def merge(self, intervals):
if not intervals:
return []
intervals.sort(key = lambda x: x[0])
n = len(intervals)
preS = intervals[0][0]
preE = intervals[0][1]
res = []
for i in range(1, n):
curS = intervals[i][0]
curE = intervals[i][1]
if curS <= preE:
preE = max(curE, preE)
else:
res.append([preS, preE])
preS = curS
preE = curE
res.append([preS, preE])
return res
Problem Solution In Java
public int[][] merge(int[][] intervals) {
if(intervals.length == 1 || intervals.length == 0) return intervals;
Arrays.sort(intervals,new Comparator<int[]>(){
public int compare(int[] o1, int[] o2){
if(o1[0] == o2[0])
return o1[1]-o2[1];
else return o1[0]-o2[0];
}
});
int start = 0;
int end = 1;
while(end < intervals.length) {
if(intervals[start][1] >= intervals[end][0]){
if(intervals[end][1] > intervals[start][1])
intervals[start][1] = intervals[end][1];
} else {
start++;
if(start != end){
intervals[start][0] = intervals[end][0];
intervals[start][1] = intervals[end][1];
}
}
end++;
}
int[][] res = new int[start+1][2];
for(int i=0;i<=start;i++)
res[i] = intervals[i];
return res;
}
Problem Solution In C++
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int > > v;
sort(intervals.begin(), intervals.end());
for(auto i: intervals) {
int st = i[0], en = i[1];
if(v.size() && st <= v.back()[1]) {
st = v.back()[0];
en = max(i[1], v.back()[1]);
v.pop_back();
}
v.push_back({st, en});
}
return v;
}
};
Problem Solution In C
int cmp(void* a,void* b){
if(((int**)a)[0][0]==((int**)b)[0][0]){
return ((int**)a)[0][1]-((int**)b)[0][1];
}
return ((int**)a)[0][0]-((int**)b)[0][0];
}
int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
*returnSize=0;
if(intervalsSize==0){
return NULL;
}
if(intervalsSize==1){
*returnSize=1;
return intervals;
}
qsort(intervals,intervalsSize,sizeof(intervals[0]),cmp);
int** ret=(int**)malloc(intervalsSize*sizeof(int*));
int* tmp=NULL;
int i=0;
tmp=intervals[0];
for(i=1;i<intervalsSize;i++){
if(tmp[1]>=intervals[i][0]){
tmp[1]=tmp[1]>intervals[i][1] ? tmp[1]: intervals[i][1];
}
else{
ret[(*returnSize)++]=tmp;
tmp=intervals[i];
}
}
if(*returnSize>0 && ret[(*returnSize-1)][1]<tmp[0]){
ret[(*returnSize)++]=tmp;
}
if(*returnSize==0){
ret[(*returnSize)++]=tmp;
}
returnColumnSizes[0]=(int*)malloc((*returnSize)*sizeof(int));
for(int i=0;i<(*returnSize);i++){
returnColumnSizes[0][i]=2;
}
return ret;
}