[LeetCode] Insert Interval (Java)

leetcode.com/problems/insert-interval/

Insert Interval - LeetCode

 

번역 : 겹치지 않는 간격에 대한 입력값이 주어지면 간격에 새 간격을 삽입합니다 (필요한 경우 병합). 간격이 처음에 시작 시간에 따라 정렬되었다고 가정 할 수 있습니다.

 

 

1. 접근 아이디어

 

• 반복문을 돌면서 intervals 배열의 첫 번째 값과 두 번째 값을 비교하면서 list에 저장합니다.
• newInterval값이 intervals 배열과의 비교에서 사용되었는지 판별하기 위해 isAvaliable 변수를 이용합니다.
• 작성한 알고리즘에서는 newInterval값이 비교되지 않고도 끝날 수 있기 때문에 list에 추가후 배열의 첫 번째 원소를 기준으로 재정렬합니다. 

 

2. 소스 코드

 

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if(intervals.length == 0) return new int[][] { newInterval }; //Edge case
        List<int[]> list = new ArrayList<>();
        boolean isAvailable = true;
        for(int i=0; i<intervals.length; i++) {
            int[] nowInterval = intervals[i];
            if(!isAvailable) {
                list.add(nowInterval);
                continue;
            }
            if(nowInterval[0] > newInterval[1]) {
                list.add(nowInterval);
                continue;
            }
            if(nowInterval[1] < newInterval[0]) list.add(nowInterval);
            else { //nowInterval[1] >= newInterval[0]
                isAvailable = false;
                int tempLeft = Math.min(nowInterval[0], newInterval[0]);
                int tempRight = Math.max(nowInterval[1], newInterval[1]);
                for(int j=i+1; j<intervals.length; j++) {
                    i++;
                    int[] nextInterval = intervals[j];
                    if(nextInterval[0] > tempRight) {
                        i--;
                        break;
                    }
                    else tempRight = Math.max(tempRight, nextInterval[1]);
                }
                list.add(new int[] { tempLeft, tempRight });
            }
        }

        if(isAvailable) {
            list.add(newInterval);
        }

        int[][] result = list.toArray(new int[][]{new int[list.size()]});
        Arrays.sort(result, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        
        return result;
    }
}