lc-56

//Given an array of intervals where intervals[i] = [starti, endi], merge all ove
//rlapping intervals, and return an array of the non-overlapping intervals that co
//ver 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] overlap, 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.
//
//
//
// Constraints:
//
//
// 1 <= intervals.length <= 104
// intervals[i].length == 2
// 0 <= starti <= endi <= 104
//
// Related Topics Array Sorting
// 👍 14993 👎 549


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) {
            return intervals;
        }

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] arr1, int[] arr2) {
                if (arr1[0] < arr2[0]) {
                    return -1;
                } else if (arr1[0] > arr2[0]) {
                    return 1;
                } else {
                    return arr1[1] - arr2[1];
                }
            }
        });

        List<int[]> resultList = new ArrayList<>();
        int[] curMergedInterval = null;

        for (int[] interval : intervals) {
            if (curMergedInterval == null) {
                curMergedInterval = new int[2];
                curMergedInterval[0] = interval[0];
                curMergedInterval[1] = interval[1];
                continue;
            }

            if (interval[0] <= curMergedInterval[1]) {
                if (interval[1] > curMergedInterval[1]) {
                    curMergedInterval[1] = interval[1];
                }
            } else {
                resultList.add(curMergedInterval);
                curMergedInterval = new int[2];
                curMergedInterval[0] = interval[0];
                curMergedInterval[1] = interval[1];
            }
        }

        resultList.add(curMergedInterval);
        return resultList.toArray(new int[resultList.size()][]);
    }
}
//leetcode submit region end(Prohibit modification and deletion)