Leet code (Medium) : 57. Insert Interval - JAVA

 

새로운 구간이 기존 구간들 중 어디 들어가야할지,

어느곳에 들어간다면 기존 구간과 겹치면 어떻게 합쳐져야할지가 중요한 문제다.

 

start를 기준으로 쫙 비교를 해서 새로운 구간보다 start가 빠른 구간들을 결과 배열에 쫙 먼저 넣는다.

새로운 구간이 결과 배열의 제일 뒤의 구간과 안겹치면 그냥 제일 뒤에 넣고,

겹치면 두 구간의 end 중 큰 구간을 결과 배열의 제일 뒤 구간의 end 값으로 함 (합치기)

그리고 나머지 구간들을 마저 넣을 때, 위 과정을 반복하며, 그냥 넣을지 합칠지 한다.

 

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int newStart = newInterval[0];
        int newEnd = newInterval[1];

        int i = 0;
        int n = intervals.length;

        List<int[]> output = new ArrayList<>();

        // newInterval 보다 시작이 빠른 모든 intervals를 output에 넣음.
        while(i < n && newStart > intervals[i][0]){
            output.add(intervals[i]);
            i++;
        }   

        // newInterval과 겹치는 구간이 없는 경우
        if(output.isEmpty() || output.get(output.size()-1)[1] < newStart){
            // output의 제일 뒤에 넣음.
            output.add(newInterval);
        } else{ // newInterval 과 겹치는 구간이 있는경우
            // newInterval과 output의 마지막 end 중 더 큰 걸 output의 마지막 end로 넣음. (합침)
            output.get(output.size()-1)[1] = Math.max(output.get(output.size() - 1)[1], newEnd);
        }
        
        // 남은 interval 들을 더함. 필요하다면 합침.
        while(i < n){
            int start = intervals[i][0];
            int end =  intervals[i][1];

            // 위랑 같음
            // 안겹치면 output에 넣고.
            if(output.get(output.size() - 1)[1] < start){
                output.add(intervals[i]);
            } else{ // 겹치면 end가 큰값을 넣음. (합침)
                output.get(output.size() - 1)[1] = Math.max(output.get(output.size() - 1)[1], end);
            }
            i++;
        }

        return output.toArray(new int[output.size()][]);
    }
}