[LeetCode] 56 Merge Intervals

Description

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.

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

---

풀이

겹치는 범위가 있다면 합쳐서 출력을 시킨다.

• 범위가 겹치는 경우 : 현재 y값 >= 다음 x값 , 겹친 범위로 다음 구간을 비교한다.
• 겹치지 않을 경우: 현재 범위를 그대로 결과값에 넣는다. 다음 범위로 넘어가 비교를 재개한다.

---

코드

class Solution {
    public int[][] merge(int[][] intervals) {
        int[][] result = new int[intervals.length][2];
        int[][] output;
        int curX, curY, index = 0;

        if (intervals.length == 1) {
            output = new int[1][2];
            output[0][0] = intervals[0][0];
            output[0][1] = intervals[0][1];
            return output;
        }

        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            } else {
                return o1[0] - o2[0];
            }
        });

        curX = intervals[0][0];
        curY = intervals[0][1];

        for (int i = 0; i < intervals.length - 1; i++) {

            if (curY >= intervals[i + 1][0]) {  // 겹칠 때
                curY = Math.max(curY, intervals[i + 1][1]);
                
                if (i == intervals.length - 2) {
                    result[index][0] = curX;
                    result[index++][1] = curY;
                }
            } else {    // 겹치지 않을 때
                result[index][0] = curX;
                result[index++][1] = curY;

                curX = intervals[i + 1][0];
                curY = intervals[i + 1][1];

                if (i == intervals.length - 2) {
                    result[index][0] = curX;
                    result[index++][1] = curY;
                }
            }
        }

        output = new int[index][2];
        for (int i = 0; i < index; i++) {
            output[i][0] = result[i][0];
            output[i][1] = result[i][1];
        }

        return output;
    }
}