[Leetcode][Java] 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.

 

intervals[i] = [starti, endi]에 해당하는 interval 배열이 주어진다.

중복되는 모든 interval을 병합하라.

그리고 중복되는 interval이 없는 배열을 반환하라, 단 입력값으로 받은 모든 interval을 커버해야 한다.

 

---

배열의 각각의 범위가 중복되는 위치를 찾아야 한다.

처음에 주어진 내용만 본다면 어떻게 해야 하는지 감이 잡히지 않는다.

우선, 주어진 배열의 startIndex기준으로 정렬을 해보자.

어느 정도 정렬이 된다면, 앞에 배열과 뒤에 배열의 값들을 비교해주면 된다.

예를 들어 intervals[0][1] > intervals[1][0] 인 경우라면 중복되는 구역이 존재하는 것이다.

중복되는 구역이 존재한다면, 두 배열을 합치고 비교를 이어가면 된다.

 

시간 복잡도는 주어진 배열을 정렬하는 시간인 O(nlogn)이 소요된다.

 

    public int[][] merge(int[][] intervals) {

        // sorting - time complex - o(nlogn)
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        int[][] rst = new int[intervals.length][2];
        rst[0] = intervals[0];
        int j = 0;
        for (int i = 1; i < intervals.length; i++) {
            if (rst[j][1] >= intervals[i][0]) {
                // join
                rst[j][1] = Math.max(rst[j][1], intervals[i][1]);
            } else {
                rst[++j] = intervals[i];
            }
        }

        int[][] r = new int[j + 1][2];
        for (int i = 0; i < j + 1; i++) {
            r[i] = rst[i];
        }

        return r;
    }