LC-0436 Medium LeetCode

436. Find Right Interval

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 54% Topics: Array, Binary Search, Sorting

Reading material

Arrays & Hashing 12 min Binary Search 12 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(n)

import bisect


class Solution(object):
    def findRightInterval(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[int]
        """
        sorted_intervals = sorted((interval.start, i) for i, interval in enumerate(intervals))
        result = []
        for interval in intervals:
            idx = bisect.bisect_left(sorted_intervals, (interval.end,))
            result.append(sorted_intervals[idx][1] if idx < len(sorted_intervals) else -1)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT