[LeetCode] Merge Intervals

리뷰

제한된 시간복잡도 O(N)을 만족하기 위해 정렬을 사용해야하는 문제.

제한된 시간복잡도를 만족하기 위해 어떻게 시간복잡도를 줄일 수 있는지 생각하는게 중요.

소요시간: 1시간

오래걸린이유: 합쳐지는 경우 인덱스 갱신 부분에서 코드 오류. 디버깅에 시간 소요.

 

 

문제 풀이   

제한

• 배열의 개수: 1~10,000  → O(N)까지 가능

 

유형

Goal: 겹치는 배열들을 모두 합치고, 최종적으로 겹치지 않는 모든 배열 i들의 [Si, Ei]를 출력

→ 시간복잡도를 고려한 구현문제

 

 

설계

1. Intervals 배열 start 오름차순 기준 정렬

∵ 한 번의 배열 탐색으로 O(N)만에 끝내기 위함

 

2. 배열 합치기

• 합쳐지는 경우 갱신 (targetStart <= compareStart <= targetEnd)
  [Si(targetStart), Ei(targetEnd)]의 Ei 갱신
• 안 합쳐지는 경우
  갱신해둔 [Si(targetStart), Ei(targetEnd)]를 기록

 

구현

class Solution {
    //O(NlogN)
    public int[][] merge(int[][] intervals) {
        sortByStartAscending(intervals);    //O(NlogN)
        List<int[]> answer = pro(intervals);    //O(N)
        return getAnswer(answer);
    }

    private void sortByStartAscending(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);
    }

    private int[][] getAnswer(List<int[]> answer) {
        int[][] ans = new int[answer.size()][2];
        for(int idx=0; idx<ans.length; idx++) {
            ans[idx][0] = answer.get(idx)[0];
            ans[idx][1] = answer.get(idx)[1];
        }
        return ans;
    }

    //O(N)
    private List<int[]> pro(int[][] intervals) {
        List<int[]> answer = new ArrayList<>();
        int targetIdx = 0;
        while(targetIdx < intervals.length) {
            int[] target = intervals[targetIdx];
            targetIdx = mergeOverlapping(target, targetIdx+1, intervals, answer);
        }
        return answer;
    }

    //return: 최초로 안합쳐진 배열의 idx
    private int mergeOverlapping(int[] target, int compareStartIdx, int[][] intervals, List<int[]> answer) {
        int targetStart = target[0];
        int targetEnd = target[1];
        for(int compareIdx=compareStartIdx; compareIdx<intervals.length; compareIdx++) {
            int[] compare = intervals[compareIdx];
            if(isOverlapping(targetStart, targetEnd, compare)) {    //합쳐지는 경우 -> targetEnd 갱신하고 다음 compare 진행
                if(compare[1] > targetEnd) {
                    targetEnd = compare[1];
                }
            } else {    //안합쳐지는 경우 -> 기록
                answer.add(new int[] {targetStart, targetEnd});
                return compareIdx;
            }
        }
        // 마지막까지 다 합쳐진 경우 -> targetEnd 갱신하고 리턴
        if(intervals[intervals.length-1][1] > targetEnd) {
            targetEnd = intervals[intervals.length-1][1];
        }
        answer.add(new int[] {targetStart, targetEnd});
        return intervals.length;
    }
    
    private boolean isOverlapping(int targetStart, int targetEnd, int[] compare) {
        return targetStart <= compare[0] && compare[0] <= targetEnd;
    }
}