Find Right Interval Python Solution with Tests

lcpy gen -n 436   # by problem number
lcpy gen -s find_right_interval   # by problem name

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

import bisect


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def find_right_interval(self, intervals: list[list[int]]) -> list[int]:
        sorted_starts = sorted((interval[0], i) for i, interval in enumerate(intervals))
        starts = [start for start, _ in sorted_starts]
        result: list[int] = []
        for interval in intervals:
            pos = bisect.bisect_left(starts, interval[1])
            result.append(sorted_starts[pos][1] if pos < len(starts) else -1)
        return result