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


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment