 LeetCode 436. Find Right Interval

Description

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

You may assume the interval’s end point is always bigger than its start point.
You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

思路

• 所有的区间的结尾不重复，因此构造一个字典，健为区间的开始位置，值为区间在原数组中的索引。
• 将所有的区间的开始位置取出来形成一个数组 starts ，对数组按照从小到大排序。
• 对于一个区间，记此区间结尾为 end，查找在 starts 数组中第一个大于等于 end 的数所在的位置 t，t 即为满足条件的区间。
• 根据 t ，找到 t 在字典中对应的值即可确定区间的位置；对所有的区间都进行此操作。
# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2020-04-11 16:08:04

from typing import List

class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
starts = []
index_dict = {}
for index, interval in enumerate(intervals):
starts.append(interval)
index_dict[interval] = index

starts.sort()

return list(self._binary_find(starts, interval, index_dict) for interval in intervals)

def _binary_find(self, nums, target, index_dict):

if target in index_dict:
return index_dict[target]

left, right = 0, len(nums) - 1
middle = left + (right - left) // 2
while left <= right:
if nums[middle] >= target and (middle == 0 or nums[middle - 1] < target):
return index_dict[nums[middle]]
elif nums[middle] < target:
left = middle + 1
elif nums[middle] >= target and (middle == 0 or nums[middle - 1] >= target):
right = middle - 1
middle = left + (right - left) // 2

return -1