56 Merge Intervals

56. 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]]
Explanation: Since intervals [1,3] and [2,6] overlaps, 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.

 public int[][] merge(int[][] intervals) {    
    
           Arrays.sort(intervals, (a,b)-> Integer.compare(a[0],b[0])); //O(nlogn)
           Stack<int[]> stack = new Stack(); //O(n)
           stack.add(intervals[0]);
        
        
        for(int i=1;i<intervals.length;i++){
            
            int startpoint2 = intervals[i][0];
            int endpoint2 = intervals[i][1];
            
            int[] poparray = stack.pop();
            
            int startpoint1 = poparray[0];
            int endpoint1 = poparray[1];
            
            int endmax = Math.max(endpoint2,endpoint1);
                
            if(endpoint1>=startpoint2){
                int[] merge = new int[]{startpoint1,endmax};
                stack.add(merge);
            }else{
                stack.add(poparray);
                stack.add(intervals[i]);
            }
             
        }
        
        int[][] output = new int[stack.size()][2];
        
        for(int i=output.length-1;i>=0;i--){
            int[] poparray = stack.pop();
            output[i][0] = poparray[0];
            output[i][1] = poparray[1];
        }
        return output;
    }