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
# @Last Modified by:   何睿
# @Last Modified time: 2020-04-11 16:34:06


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[0])
            index_dict[interval[0]] = index

        starts.sort()

        return list(self._binary_find(starts, interval[1], 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

源代码文件在 这里 。


©本文是原创文章,欢迎转载,转载需保留 文章来源 ,作者信息和本声明.

Posted in LeetCode and tagged , .

花若盛開,蝴蝶自來. 分享学习,每天进步一点点

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.