올바른 간격 찾기

intervals 의 배열이 주어집니다. 여기서 intervals[i] = [starti, endi] 및 각 starti은 고유합니다.

간격i의 올바른 간격은 j 및 startj >= endi가 최소화되는 간격startj입니다. i는 j와 같을 수 있습니다.

각 간격에 대한 오른쪽 간격 인덱스의 배열을 반환합니다i. 간격 i 에 대한 올바른 간격이 없으면 인덱스 -1 에 i 를 넣습니다.

예 1:

입력: 간격 = [[1,2]]
출력: [-1]
설명: 콜렉션에는 하나의 간격만 있으므로 -1을 출력합니다.

예 2:

입력: 간격 = [[3,4],[2,3],[1,2]]
출력: [-1,0,1]
설명: [3,4]에 대한 올바른 간격이 없습니다.
start0 = 3이 >= end1 = 3인 가장 작은 시작이므로 [2,3]의 올바른 간격은 [3,4]입니다.
start1 = 2가 >= end2 = 2인 가장 작은 시작이므로 [1,2]의 올바른 간격은 [2,3]입니다.

예 3:

입력: 간격 = [[1,4],[2,3],[3,4]]
출력: [-1,2,-1]
설명: [1,4]와 [3,4]에 올바른 간격이 없습니다.
start2 = 3이 >= end1 = 3인 가장 작은 시작이므로 [2,3]의 올바른 간격은 [3,4]입니다.

제약:

1 <= intervals.length <= 2 * 104

intervals[i].length == 2

-106 <= starti <= endi <= 106

각 간격의 시작점은 고유합니다.

해결책:

import bisect

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        ans = [-1 for i in range(n)]
        starts = []
        ends = []
        for k in range(n):
            i, j = intervals[k]
            bisect.insort(starts, (i, k))
            bisect.insort(ends, (j, k))
        sinx = [s[0] for s in starts]
        lst = len(starts)
        for end, i in ends:
            pos = bisect.bisect_left(sinx, end)
            if pos < lst:
                ans[i] = starts[pos][1]
        return ans