Merge Intervals Problem Solution

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

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;
    }