Find Right Interval

Problem Id: 436 Difficulty: Medium


Intuition

Solution


class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        starts = [i[0] for i in intervals]
        ends = [i[1] for i in intervals]
        starts.sort()
        ends.sort()
        end_mapping = {}
        index = 0
        for end in ends:
            while index < n and end > starts[index]:
                index += 1
            if index == n:
                break
            end_mapping[end] = starts[index]

        start_index = {interval[0]: i for i, interval in enumerate(intervals)}
        ans = []
        for start, end in intervals:
            if end not in end_mapping:
                ans.append(-1)
            else:
                ans.append(start_index[end_mapping[end]])
        return ans