56. Merge Intervals

class Solution {
    public int[][] merge(int[][] intervals) {
        
        if (intervals.length <= 1) {
            return intervals;
        }
        
        Arrays.sort(intervals, new Comparator<int[]> () {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        
        List<int[]> mergedIntervals = new ArrayList<>();
        int[] interval = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            int[] curInterval = intervals[i];
            if (interval[1] >= curInterval[0]) {
                interval = new int[]{interval[0], Math.max(interval[1], curInterval[1])};
            } else {
                mergedIntervals.add(interval);
                interval = curInterval;
            }
        }
        mergedIntervals.add(interval);
        return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        
        for (int i = 0; i < intervals.length; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        
        Arrays.sort(start);
        Arrays.sort(end);
        
        ArrayList<int[]> newIntervals = new ArrayList<>();
                    
        int i = 0;
        while (i < start.length) {
            int curStart = start[i];
            int curEnd = end[i];
            int j = i + 1;
            while (j < start.length) {
                if (start[j] <= curEnd) {
                    curEnd = end[j];
                    i++;
                    j++;
                } else {
                    break;
                }
            }
            newIntervals.add(new int[]{curStart, curEnd});
            i++;
        }
        
        int[][] res = new int[newIntervals.size()][2];
        
        for (int k = 0; k < newIntervals.size(); k++) {
            res[k] = new int[]{newIntervals.get(k)[0], newIntervals.get(k)[1]};
        }
        return res;
    }
}