[LeetCode] 56. Merge Intervals

LeetCode의 문제와 유저들이 등록한 코드 중 득표수가 가장 높은 코드 분석

 

Given a collection of intervals, merge all overlapping intervals.

시작점과 끝점이 있는 숫자 쌍의 리스트 중 겹치는 부분이 있는 것을 병합하기

 

Example 1:

Input: [[1,3], [2,6], [8,10], [15,18]]

Output: [[1,6], [8,10], [15,18]]

Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

[1,3]과  [2,6] 은 [1,6]로 병합

 

Example 2:

Input: [[1,4], [4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

[1,4]과 [4,5]는 [1,5]로 병합

 

class Solution {
    public int[][] merge(int[][] intervals) {
        if (intervals.length <= 1)
            return intervals;
            
        // Sort by ascending starting point
        Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));

        List<int[]> result = new ArrayList<>();
        int[] newInterval = intervals[0];
        result.add(newInterval);
        for (int[] interval : intervals) {
            if (interval[0] <= newInterval[1]) // Overlapping intervals, move the end if needed
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            else {                             // Disjoint intervals, add the new interval to the list
                newInterval = interval;
                result.add(newInterval);
            }
        }

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

 

풀이 방법

 

1. intervals 배열을 시작점이 작은 순서대로 정렬한 뒤 처음에 위치한 숫자 쌍을 기준값으로 설정한다. 

2. intervals 배열을 반복문을 돌면서 나오는 숫자 쌍의 시작점과 기준값의 종료점을 비교한다. 

3. 값의 비교

  3-1.  기준값의 종료점이 더 크거나 같은 경우

    - 범위가 겹치는 경우 이므로 종료점이 더 큰 것을 추출하여 기준값을 재정의 한다. 

    - ex) 기준값: [1,2], 비교대상 [1,3]인 경우

  3-2. 기준값의 종료점이 더 작은 경우

    - 범위가 겹치지 않는 경우 이므로 기준값과 비교한 숫자 쌍을 새로운 기준값으로 정의하고 결괏값을 저장하는 리스트에도 추가한다.

    - ex) 기준값: [1,6], 비교대상 [14,16]인 경우

 

 

코드 동작 확인

 

Input: [[2,6], [1,3], [8,10], [15,18]]

 

1. intervals 배열을 시작점이 작은 순서대로 정렬

- [[2,6], [1,3], [8,10], [15,18]][1,3], => [[1,3], [2,6], [8,10], [15,18]]

2. 결괏값을 담을 리스트를 생성 후 정렬한 intervals 배열의 처음에 위치한 값으로 설정

- [[1,3]]

3. intervals 배열을 루프 돌면서 엘리먼트들의 시작점이 기준값의 끝점보다 작거나 같은지 비교

 

최초

> newInterval = [1,3]

> intervals =  [[1,3], [2,6], [8,10], [15,18]]
> result = [[1,3]]

 

루프 1차 비교 

> newInterval = [1,3]

> interval =  [1,3]

> result = [[1,3]]

[1] <= [3]   interval의 시작점이 newInterval의 끝점보다 작기 때문에 newInterval [1] = Math.max(3, 3) 

> newInterval = [1,3]으로 변화 없음

 

루프 2차 비교 

> newInterval = [1,3]

> interval =  [2,6]

> result = [[1,3]]

[2] <= [3]   interval의 시작점이 newInterval의 끝점보다 작기 때문에 newInterval [1] = Math.max(3, 6) 

> newInterval = [1,6]

> result = [[1,6]]

 

루프 3차 비교 

> newInterval = [1,6]

> interval =  [8,10]

> result = [[1,6]]

[8] <= [6]  interval의 시작점이 newInterval의 끝점보다 크기 때문에 newInterval =  [8,10]

> newInterval = [8,10]

> result = [[1,6][8,10]]

 

루프 4차 비교 

> newInterval = [1,10]

> interval =  [15,18]

> result = [[1,6][8,10]]

[15] <= [10]   interval의 시작점이 newInterval의 끝점보다 크기 때문에 newInterval [1] = Math.max(10, 18) 

> newInterval = [1,10]

> result = [[1,6][8,10], [15,18]]

 

종료