[LeetCode] 56. Merge Intervals - Java

https://leetcode.com/problems/merge-intervals/description/

Merge Intervals - LeetCode

---

문제

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

 

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

---

풀이

풀이 과정

시작점과 종료점으로 이루어진 인터벌이 리스트로 주어질 때 겹치는 인터벌들을 합쳐 새로운 인터벌 리스트를 반환해야한다.

우선 배열의 길이가 1 이하인 경우에는 합칠 필요가 없으므로 전달받은 인터벌 배열을 그대로 return 한다.

// intervals 배열의 길이가 1 이하인 경우 merge할 필요가 없으므로 바로 return
if(intervals.length <= 1) return intervals;

 

전달받은 인터벌 배열은 정렬되지 않은 상태이기 때문에 탐색을 쉽게 하기 위하여 오름차순으로 정렬한다.

// 인터벌 오름차순 정렬
Arrays.sort(intervals, (o1, o2) -> { return o1[0] - o2[0]; });

 

겹치는 인터벌들을 합쳐 새롭게 만들 인터벌들을 저장하기위한 리스트를 선언한다.

// 결과 값을 저장할 리스트
List<int[]> resultList = new ArrayList<>();

 

합치는 과정은 다음과 같다.

이전 인터벌과 현재 인터벌을 두고 이전 인터벌의 종료점과 현재 인터벌의 시작점을 비교한다.
이전 인터벌은 배열의 첫 번째 값으로 초기화하고 두 번째 값 부터 탐색을 시작한다.
이전 인터벌이 현재 인터벌보다 앞에 있는 경우에는 이전 인터벌을 그대로 결과 리스트에 추가한다.
만약 이전 인터벌과 현재 인터벌이 겹치는 경우에는 이전 인터벌의 종료점을 두 인터벌의 종료점 중 큰 값으로 갱신하고 다음 인터벌 탐색을 계속한다.

// 이전 인터벌 선언 및 intervals 배열의 첫 번째 값으로 설정
int[] prevInterval = intervals[0];

// 두 번째 요소부터 탐색
for(int i = 1; i < intervals.length; i++) {
    // 이전 인터벌이 현재 탐색중인 인터벌보다 앞에 있는 경우
    if(prevInterval[1] < intervals[i][0]) {
        // 이전 인터벌을 결과 리스트에 추가
        resultList.add(prevInterval);
        // 이전 인터벌을 현재 탐색중인 인터벌로 갱신
        prevInterval = intervals[i];
    }
    // 이전 인터벌과 현재 탐색중인 인터벌이 겹치는 경우
    else {
        // 이전 인터벌의 종료점을 두 인터벌의 종료점 중 큰 값으로 갱신
        prevInterval[1] = Math.max(prevInterval[1], intervals[i][1]);
    }
}

 

탐색을 마치게 되면 이전 인터벌에 배열의 맨 마지막 인터벌이 하나 남게되는데 마지막 남은 인터벌을 결과 리스트에 추가해주고 배열로 변환하여 최종 return 한다.

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

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

---

최종 코드

class Solution {
    public int[][] merge(int[][] intervals) {
        // intervals 배열의 길이가 1 이하인 경우 merge할 필요가 없으므로 바로 return
        if(intervals.length <= 1) return intervals;
        
        // 인터벌 오름차순 정렬
        Arrays.sort(intervals, (o1, o2) -> { return o1[0] - o2[0]; });

        // 결과 값을 저장할 리스트
        List<int[]> resultList = new ArrayList<>();
        
        // 이전 인터벌 선언 및 intervals 배열의 첫 번째 값으로 설정
        int[] prevInterval = intervals[0];
        
        // 두 번째 요소부터 탐색
        for(int i = 1; i < intervals.length; i++) {
            // 이전 인터벌이 현재 탐색중인 인터벌보다 앞에 있는 경우
            if(prevInterval[1] < intervals[i][0]) {
                // 이전 인터벌을 결과 리스트에 추가
                resultList.add(prevInterval);
                // 이전 인터벌을 현재 탐색중인 인터벌로 갱신
                prevInterval = intervals[i];
            }
            // 이전 인터벌과 현재 탐색중인 인터벌이 겹치는 경우
            else {
                // 이전 인터벌의 종료점을 두 인터벌의 종료점 중 큰 값으로 갱신
                prevInterval[1] = Math.max(prevInterval[1], intervals[i][1]);
            }
        }
        
        // 마지막 남은 인터벌을 리스트에 추가
        resultList.add(prevInterval);
        
        // 리스트를 배열로 변환하여 반환
        return resultList.toArray(new int[resultList.size()][]);
    }
}

---