99클럽 코테 스터디 30일차 TIL + 오늘의 학습 키워드

☑️ 문제(Leetcode): 436. Find Right Interval

https://leetcode.com/problems/find-right-interval/description/

 

☑️ 문제 이해

오른쪽 인터벌(right interval)이란?

 

interval[i]의 오른쪽 인터벌은 다음 조건을 만족하는 interval[j]와의 간격 값이다.

1. start_j >= end_i
2. start_j는 모든 interval의 start 중 최솟값 (이 때 start는 유일한 값이라 중복되지 않는다.)

 

☑️ Code

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int length = intervals.length;
        int[][] startIndexes = new int[length][2];
        for (int i = 0; i < length; i++) {
            startIndexes[i][0] = intervals[i][0];
            startIndexes[i][1] = i;
        }
        
        Arrays.sort(startIndexes, (x, y) -> x[0] - y[0]);

        int[] answer = new int[length];
        for (int i = 0; i < length; i++) {
            int j = binarySearch(startIndexes, intervals[i][1]);
            answer[i] = j < length ? startIndexes[j][1] : -1;
        }
        return answer;
    }

    private int binarySearch(int[][] arr, int n) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid][0] >= n) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}