[leetcode] 56. Merge Intervals

겹치는 구간을 합치는 문제입니다.

leetcode.com/problems/merge-intervals/

Merge Intervals - LeetCode

이 문제의 핵심은 처리해야 할 구간 배열에 대해 정렬을 먼저 하는 것입니다.

시작 시간을 기준으로 입력된 값을 정렬합니다.

먼저 병합된 결과값을 저장하는 변수를 선언하고 정렬된 배열의 전체를 처음부터 탐색합니다.

만약에 병합된 결과값의 마지막으로 들어간 값의 종료시간보다 탐색 중인 배열의 시작시간이 더 작거나 같다면,

마지막 병합된 결과값에 합칩니다. 그렇지 않다면 새로운 결과값이므로 결과값에 추가해줍니다.

 

시간복잡도는 제일 처음 Arrays.sort()를 사용했으므로 O(NlogN)이 될 것이고, 공간복잡도는 O(N) 입니다.

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));

        List<int[]> list = new ArrayList<>();
        list.add(intervals[0]);

        for(int i=1; i<intervals.length; i++) {
            int start = intervals[i][0];
            int end = intervals[i][1];
            
            int[] last = list.get(list.size()-1);
            int lastEnd = last[1];
            
            if(start <= lastEnd) {
                last[1] = Math.max(lastEnd, end);
            } else {
                list.add(intervals[i]);
            }
        }
        
        int[][] res = new int[list.size()][2];
        for(int i=0; i<list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}