Interval 개념 및 특징

개념

Interval은 구간 배열 or 리스트가 주어지며, 구간을 삽입, 삭제, 병합 하는 문제가 주어진다.

 

 

특징

관련 문제 유형은 다음 세가지로 볼 수 있다.

1. 새로운 구간 하나를 구간들 사이에 넣기.
2. 구간들의 겹치는 부분을 정리하기.
3. 최대 겹치는 구간 길이 구하기.

이때, 각 구간은 [시작점, 끝점]의 형식으로 시작점과 끝점이 배열로 정의되어 있다.

 

interval 문제는 정렬이 중요하다.

구간 배열이 intervals라고 하면 시작점이나 끝점을 기준으로 오름차순 정렬을 하는 것이 기본이다.

// start 기준 오름차순 정렬
Arrays.sort(intervals, (a,b) -> Integer.compare(a[0], b[0]);

// end 기준 오름차순 정렬
Arrays.sort(intervals, (a,b) -> Integer.compare(a[1], b[1]);

 

무엇을 기준으로 하느냐는 문제유형에 따라 달라질 수 있다.

 

1번 유형은 구간끼리 겹치는 부분이 있으면, 두 구간을 하나로 합치는 식으로 진행된다.

2번 유형은 새로운 구간을 적절한 위치에 삽입 해야 하는데, 이때 겹치는 구간은 합치며 진행된다.

3번 유형은 겹치는 구간중 최대 구간을 구해야 한다.

1,2,3번 유형은 시작점, 끝점 둘다 상관없지만 시작점 기준 오름차순이 더 직관적이고, 효율적이다.

 

 

 

그러나 끝점 기준 오름차순 정렬이 효율적일 때도 있다.

예시로 다음 문제를 보자.

 

이 문제는 모든 풍선을 터뜨리기 위해 필요한 화살의 수를 구하는 문제이다.

구간이 겹치는 것을 최대한 활용해 최소한의 화살로 모든 구간을 커버해야하기 때문에,

현재 가장 빨리 끝나는 지점에 화살을 쏘아 그 지점을 기준으로 겹치는 구간을 최대한 많이 포함시키는 방식이 유리하다.

왜 끝점 기준으로 정렬하는 것이 적합한가?

끝점 기준으로 정렬하면 현재 끝나는 지점을 기준으로 이후 구간들을 처리할 수 있어서,

화살을 쏘아야 하는 최소 횟수를 쉽게 계산할 수 있다.

1. 끝점 기준으로 오름차순 정렬 후 최소 화살 구하기:
   • 먼저 구간을 끝점 기준으로 정렬하면, 각 구간이 겹칠 수 있는 최대 지점(겹치는 구간 끝점)이 연속적으로 배치된다.
   • 이렇게 하면 현재 끝점에서부터 그 다음 시작점이 현재 끝점보다 뒤에 있는지 확인하면서,
     더 이상 겹칠 수 없는 구간이 나오면 화살을 추가로 쏘아야 한다는 것을 쉽게 판단할 수 있다.
2. 현재 구간의 끝을 기준으로 이후 구간들과의 겹침을 확인:
   • 끝점 기준으로 정렬된 상태에서는 이전 끝점과 겹치지 않는 구간이 나타날 때만 새로운 화살이 필요하다.
   • 따라서, 연속된 끝점을 기준으로 최대한 많은 구간을 커버하고, 겹치지 않는 구간이 나타날 때만 화살을 추가하는 방식으로 최소 화살 수를 구할 수 있다.

 

풀이는 다음과 같다.

class Solution {
    public int findMinArrowShots(int[][] points) {
        int res = 1;

        // 끝점기준 오름차순 정렬
        Arrays.sort(points, (a,b) -> Integer.compare(a[1], b[1])); 
        // a[1] - b[1] 는 값 중 하나가 음수면 오버플로가 발생할 수 있어서
        // Integer.compare(a[1], b[1]) 를 쓰는 것이 안전하다.

        int end = points[0][1];

        for(int i = 1; i < points.length; i++){
            int nowStart = points[i][0];
            int nowEnd = points[i][1];

            // 지금까지 구간들의 중복 구간과 겹치지 않는 구간일 때
            if(end < nowStart){
                end = nowEnd;
                res++;
            }
        }

        return res;
    }
}