LeetCode 436. Find Right Interval – 二分查找（Binary Search）系列题24

You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example 1:

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

Example 2:

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.

Example 3:

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.

Constraints:

• 1 <= intervals.length <= 2 * 104
• intervals[i].length == 2
• -106 <= starti <= endi <= 106
• The start point of each interval is unique.

题目大意： 给定一个区间数组intervals[i] = [starti, endi]，并且规定数组里的各区间起点starti是唯一的。对右区间right interval的定义是：对于一个区间intervals[i]，它的右区间intervals[j]是数组里所有满足startj>=endi的区间里startj最小的那个区间。现在要求返回每个区间的右区间对应的数组索引，如果不存在则返回-1。

解题思路：要找right interval最简单的方法就是遍历整个数组，一遇到startj>=endi的区间就比较更新，最后得到具有最小startj的那个区间。但是如果数组是按starti排好序的，那就只要找到第一个（最左边的）满足startj>=endi的区间即可，这其实也就是有序数组的下届lower bound的概念，因此可以先把数组按starti排好序然后用二分查找法查找endi的下届lower bound。

注：题目要求返回数组下标，但排序后区间的索引就变了，因此要在排序前用一个map来记录区间对应原数组的索引。

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        n = len(intervals)
        indexMap = {}
        for i in range(n):
            indexMap[tuple(intervals[i])] = i
        intervals.sort()
        
        def lowerBound(target):
            l, r = 0, n - 1
            while l <= r:
                mid = (l + r) // 2
                if target <= intervals[mid][0]:
                    r = mid - 1
                else:
                    l = mid + 1
            return l
                    
        res = [-1] * n
        for interval in intervals:
            lb = lowerBound(interval[1])
            if lb < n:
                res[indexMap[tuple(interval)]] = indexMap[tuple(intervals[lb])]
        
        return res