[PS] 99클럽 코테 스터디 30일차 TIL (Find Right Interval)

문제

문제 링크

설명

문제에서 n 개의 인터벌들이 주어진다. 각 인터벌은 [start, end] 형태로 주어지며, start는 구간의 시작점, end는 구간의 끝점을 나타낸다.

풀이

class Solution {
  public int[] findRightInterval(int[][] intervals) {
    int n = intervals.length;
    int[][] indexArr = new int[n][2];
    
    // 인덱스 저장
    for (int i = 0; i < indexArr.length; i++) {
      indexArr[i][0] = intervals[i][0];  // start
      indexArr[i][1] = i;  // index
    }

    // start 를 기준으로 정렬
    Arrays.sort(indexArr, (o1, o2) -> Integer.compare(o1[0], o2[0]));

    int[] result = new int[n];
    for (int i = 0; i < n; i++) {
      int end = intervals[i][1];
      int search = binarySearch(indexArr, end);
      result[i] = search;
    }

    return result;
  }

  // 
  private int binarySearch(int[][] indexArr, int end) {
    int left = 0, right = indexArr.length;
    
    while (left < right) {
      int mid = left + (right - left) / 2;
      int start = indexArr[mid][0];
      
      if (start < end) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    return left < indexArr.length ? indexArr[left][1] : -1;
  }
}

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