🔥[99클럽 코테 스터디] 30일차 TIL - Find Right Interval

⏳문제

You are given an array of intervals, where intervals[i] = [start$_i$, end$_i$] and each start$_i$ is unique.

The right interval for an interval i is an interval j such that start$_j$ >= end$_i$ and start$_j$ is minimized. Note that i may equal j.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

📃입출력 예

입출력 예 #1

Input	Output
intervals = [[1,2]]	[-1]

There is only one interval in the collection, so it outputs -1.

입출력 예 #2

Input	Output
intervals = [[3,4],[2,3],[1,2]]	[-1,0,1]

There is no right interval for [3,4]. The right interval for [2,3] is [3,4] since start$_0$ = 3 is the smallest start that is >= end$_1$ = 3. The right interval for [1,2] is [2,3] since start$_1$ = 2 is the smallest start that is >= end$_2$ = 2.

입출력 예 #3

Input	Output
intervals = [[1,4],[2,3],[3,4]]	[-1,2,-1]

There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start$_2$ = 3 is the smallest start that is >= end$_1$ = 3.

🚨제한 사항

• 1 <= intervals.length <= 2 * 104
• intervals[i].length == 2
• -10$^6$ <= start$_i$ <= end$_i$ <= 106`
• The start point of each interval is unique.

---

✏️풀이

🤔문제의 목표

이 문제는 시작점과 끝점으로 이루어진 여러 개의 구간 중에서, 각 구간의 끝점보다 크거나 같은 시작점을 가진 구간을 찾는 것이다. 단, 만약 그런 구간이 없다면 -1을 반환해야 한다.

예를 들어, 구간 배열이 다음과 같다고 가정해보자

intervals = [[1, 2], [2, 3], [0, 1]]

이 배열애서 각 구간을 살펴보면

1. 첫 번째 구간 [1, 2]

끝점이 2이기 때문에, 시작점이 2 이상인 구간을 찾아야 한다.
여기서는 두 번째 구간 [2, 3]이 해당된다.
따라서 인덱스 1을 반환한다.

2. 두 번째 구간 [2, 3]

끝점이 3이기 때문에, 시작점이 3 이상인 구간을 찾아야 한다.
하지만 주어진 구간 중에서는 그런 구간이 없다.
따라서 -1을 반환한다.

3. 세 번째 구간 [0, 1]

끝점이 1이기 때문에, 시작점이 1 이상인 구간을 찾아야 한다.
여기서는 첫 번째 구간 [1, 2]가 해당된다.
따라서 인덱스 0을 반환한다.

최종 결과

이 모든 것을 종합하면, 각 구간에 대한 결과는 다음과 같다.

• 첫 번째 구간 : 1
• 두 번째 구간 : -1
• 세 번째 구간 : 0

따라서 최종적으로 반환되는 배열은 [1, -1, 0]이 된다.

🤔접근 방법

• 각 구간의 끝점에 대해, 그 끝점보다 크거나 같은 시작점을 가진 구간을 찾기 위해 이진 탐색을 사용하는 것이 더 효율적이다.
• 이진 탐색을 하기 위해서는 배열이 정렬되어 있어야 하기 때문에, 각 구간의 시작점과 끝점을 기준으로 정렬을 해야 한다.
• 이진 탐색을 통해 찾은 인덱슬르 결과 배열에 저장하고, 해당 구간이 없다면 -1을 저장한다.

이진 탐색에 대한 개념은 따로 찾아서 정리를 해 보았다.

👾최종 코드

// intervals 예시 : [[3,4], [2,3], [1,2]]

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int[] answer = new int[intervals.length];
        HashMap<Integer, Integer> startIndexMap = new HashMap<>();

        // 시작점과 인덱스를 매핑하여 저장
        for (int i = 0; i < intervals.length; i++) {
            startIndexMap.put(intervals[i][0], i);
        }

        // startIndexMap
        // Key -> Value
        // 3 -> 0
        // 2 -> 1
        // 1 -> 2

        // 시작점 배열을 정렬
        int[][] sortedIntervals = new int[intervals.length][2];
        for (int i = 0; i < intervals.length; i++) {
            sortedIntervals[i] = intervals[i];
        }
        Arrays.sort(sortedIntervals, (a, b) -> Integer.compare(a[0], b[0]));

        // sortedIntervals
        // [[1,2], [2,3], [3,4]]

        // 각 구간의 끝점에 대해 이진 탐색
        for (int i = 0; i < intervals.length; i++) {
            int end = intervals[i][1];
            int index = binarySearch(sortedIntervals, end);
            if (index == -1) {
                answer[i] = -1;
            }
            else {
                answer[i] = startIndexMap.get(sortedIntervals[index][0]);
            }
        }

        return answer;                      
    }

    // 이진 탐색
    public int binarySearch(int[][] intervals, int target) {
        int left = 0;
        int right = intervals.length - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (intervals[mid][0] >= target) {
                result = mid; // 가능한 인덱스 저장
                right = mid - 1; // 더 작은 인덱스를 찾기 위해 왼쪽으로 이동
            }
            else {
                left = mid + 1; // 더 큰 인덱스를 찾기 위해 오른쪽으로 이동
            }
        }
        
        return result;
    }
}

1. startIndexMap을 사용하여 각 시작점과 그에 해당하는 인덱스를 저장한다.
2. sortedIntervals 배열을 시작점 기준으로 정렬한다.
3. 각 구간의 끝점에 대해 이진 탐색을 수행하여, 그 끝점보다 크거나 같은 시작점을 가진 구간의 인덱스를 찾는다
4. 찾은 인덱스를 결과 배열에 저장한다. 만약 해당 구간이 없다면 -1을 저장한다.

---

🔗문제 링크
💻Repository