Merge Intervals

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

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Stack;
public class MergeIntervals {
    public static void main(String[] args) {
        int intervals[][] = { { 1, 3 }, { 2, 6 }, { 8, 10 }, { 15, 18 } };
        int res[][] = merge(intervals);
        System.out.println(Arrays.deepToString(res));
    }
    static int[][] merge(int[][] v) {
        List<int[]> res = new ArrayList<int[]>();
        Arrays.sort(v, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        if (v.length == 0)
            return res.toArray(new int[0][2]);
        Stack<int[]> st = new Stack<int[]>();
        st.add(new int[] { v[0][0], v[0][1] });
        for (int i = 1; i < v.length; i++) {
            int p[] = st.peek();
            if (p[1] < v[i][0])
                st.add(new int[] { v[i][0], v[i][1] });
            else {
                if (p[1] < v[i][1])
                    p[1] = v[i][1];
                st.pop();
                st.push(p);
            }
        }
        while (!st.isEmpty()) {
            int p[] = st.pop();
            res.add(p);
        }
        return res.toArray(new int[0][2]);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> merge(vector<vector<int>>& v) 
{
        vector<vector<int>> res;
        sort(v.begin(),v.end());
        if(v.size()==0)
              return res;
        stack<pair<int,int>>st;
        st.push({v[0][0],v[0][1]});
        for(int i=1;i<v.size();i++)
        {
            pair<int,int> p=st.top();
            if(p.second<v[i][0])
                  st.push({v[i][0],v[i][1]});
            else
            {
                if(p.second<v[i][1])
                      p.second=v[i][1];
                st.pop();
                st.push(p);
            }
        }
        while(!st.empty())
        {
            pair<int,int> p=st.top();
            st.pop();
            vector<int> x;
            x.push_back(p.first);
            x.push_back(p.second);
            res.push_back(x);
        }
        reverse(res.begin(),res.end());
        return res;
}
int main()
{
   vector<vector<int>> intervals ={{1,3},{2,6},{8,10},{15,18}};
   intervals=merge(intervals);
   cout<<"[";
   for(int i=0;i<intervals.size();i++)
     {
         cout<<"[";
         cout<<intervals[i][0]<<","<<intervals[i][1];
         cout<<"]";
         if(i!=intervals.size()-1)
            cout<<",";
     }
    cout<<"]";
}