[LeetCode] 57. Insert Interval - Java

https://leetcode.com/problems/insert-interval/description/

Insert Interval - LeetCode

---

문제

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

 

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

 

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 105

---

풀이

풀이 과정

각각 시작점과 종료점으로 이루어진 인터벌들의 배열이 주어지고 하나의 새로운 인터벌이 주어질 때 새로운 인터벌을 기존 인터벌 배열과 합쳐 반환해야하는 문제이다.
인터벌끼리 범위가 겹치는 경우에는 겹치는 인터벌을 하나로 합친 새로운 인터벌로 반환해야한다.
주어진 인터벌 배열은 오름차순으로 정렬되어 있으며 겹치는 인터벌을 존재하지 않는다.
새롭게 반환되는 배열 역시 오름차순으로 정렬되어야하며 범위가 겹치는 인터벌이 존재해서는 안된다.

결과로 반환할 인터벌 리스트를 하나 선언한다. 마지막에 배열로 변환하여 반환한다.

// 새로 합친 인터벌을 저장할 리스트
List<int[]> resultList = new ArrayList<>();

 

newInterval을 합칠 대상 인터벌로 보고, intervals 배열의 모든 인터벌에 대해 다음 세 가지 경우를 비교한다.

1. 합칠 대상 인터벌이 탐색중인 인터벌보다 뒤에 있는 경우
2. 합칠 대상 인터벌이 탐색중인 인터벌보다 앞에 있는 경우
3. 합칠 대상 인터벌과 탐색중인 인터벌이 겹치는 경우 

합칠 대상 인터벌이 탐색중인 인터벌보다 뒤에 있는 경우에는 탐색중인 인터벌을 결과 리스트에 추가한다.

합칠 대상 인터벌이 탐색중인 인터벌보다 앞에 있는 경우에는 합칠 대상 인터벌을 결과 리스트에 추가하고 현재 탐색중인 인터벌을 합칠 대상 인터벌로 갱신한다.

합칠 대상 인터벌이 탐색중인 인터벌이 겹치는 경우에는 두 인터벌을 하나로 합친다.
두 인터벌의 시작점 중 적은 값을 시작점으로 하고 종료점 중 큰 값을 종료점으로 하는 인터벌을 합칠 대상 인터벌로 갱신한다.

// 모든 인터벌 탐색
for(int[] interval : intervals) {
    // 합칠 대상 인터벌이 탐색중인 인터벌보다 뒤에 있는 경우
    if(newInterval[0] > interval[1]) {
        // 현재 탐색중인 인터벌을 리스트에 추가
        resultList.add(interval);
    }
    // 합칠 대상 인터벌이 탐색중인 인터벌보다 앞에 있는 경우
    else if(interval[0] > newInterval[1]){
        // 합칠 대상 인터벌을 리스트에 추가
        resultList.add(newInterval);
        // 합칠 대상 인터벌을 현재 탐색 인터벌로 갱신
        newInterval = interval;
    }
    // 합칠 대상 인터벌과 탐색중인 인터벌이 겹치는 경우 
    else {
        // 합칠 대상 인터벌의 시작점과 종료점을 각각 최소, 최대값으로 갱신
        newInterval[0] = Math.min(interval[0], newInterval[0]);
        newInterval[1] = Math.max(interval[1], newInterval[1]);
    }
}

 

intervals 배열을 순회하고 newInterval에 남은 마지막 인터벌을 결과 리스트에 추가한다.

// 마지막 남은 인터벌을 리스트에 추가
resultList.add(newInterval);

 

만들어진 리스트를 배열로 변환하여 최종 반환한다.

// 리스트를 배열로 변환하여 반환
return resultList.toArray(new int[resultList.size()][]);

---

최종 코드

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        // 새로 합친 인터벌을 저장할 리스트
        List<int[]> resultList = new ArrayList<>();
        // 모든 인터벌 탐색
        for(int[] interval : intervals) {
            // 합칠 대상 인터벌이 탐색중인 인터벌보다 뒤에 있는 경우
            if(newInterval[0] > interval[1]) {
                // 현재 탐색중인 인터벌을 리스트에 추가
                resultList.add(interval);
            }
            // 합칠 대상 인터벌이 탐색중인 인터벌보다 앞에 있는 경우
            else if(interval[0] > newInterval[1]){
                // 합칠 대상 인터벌을 리스트에 추가
                resultList.add(newInterval);
                // 합칠 대상 인터벌을 현재 탐색 인터벌로 갱신
                newInterval = interval;
            }
            // 합칠 대상 인터벌과 탐색중인 인터벌이 겹치는 경우 
            else {
                // 합칠 대상 인터벌의 시작점과 종료점을 각각 최소, 최대값으로 갱신
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }
        }
        
        // 마지막 남은 인터벌을 리스트에 추가
        resultList.add(newInterval);
        
        // 리스트를 배열로 변환하여 반환
        return resultList.toArray(new int[resultList.size()][]);
    }
}

---