436.Find Right Interval

Tags: [binary_search], [sort]

Link: https://leetcode.com/problems/find-right-interval/?tab=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:

1. You may assume the interval's end point is always bigger than its start point.
2. 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.

Solution: sort, binary_search

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def findRightInterval(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[int]
        """
        start_to_index_arr = [(interval.start, i) for (i, interval) in enumerate(intervals)]
        start_to_index_arr = sorted(start_to_index_arr)

        result = []
        for interval in intervals:
            left_insert_index = bisect.bisect_left(start_to_index_arr, (interval.end,))
            if left_insert_index < len(intervals):
                original_index = start_to_index_arr[left_insert_index][1]
                result.append(original_index)
            else:
                result.append(-1)

        return result

Revelation:

• Try to be familiar with the Python's bisect.bisect.left() and bisect.bisect_right().
• Try to be familiar with the Python's enumerate.
• We can use binary search to seek the exact target, and we can also use binary search to seek a range.

Note:

• Time complexity = O(nlgn), n is the number of the elements in the given array.

Time Limited Exceeded

# Definition for an interval.
class Interval(object):
    def __init__(self, s=0, e=0):
        self.start = s
        self.end = e

class Solution(object):
    def findRightInterval(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[int]
        """
        if not intervals:
            return []

        start_to_original_index_map = {}
        for i in xrange(len(intervals)):
            start_to_original_index_map[intervals[i].start] = i

        intervals = sorted(intervals, cmp=self.compare_start)
        result = [-1 for _ in xrange(len(intervals))]
        for interval in intervals:
            target_interval = self.binary_search(intervals, interval.end)
            if target_interval:
                result[start_to_original_index_map[interval.start]] = start_to_original_index_map[target_interval.start]

        return result

    @staticmethod
    def compare_start(interval_1, interval_2):
        return interval_1.start - interval_2.start

    @staticmethod
    def binary_search(intervals, target_end):
        if not intervals or target_end is None:
            return None

        start = 0
        end = len(intervals) - 1
        while start <= end:
            mid = (start + end) / 2
            interval = intervals[mid]

            if interval.start == target_end:
                return interval
            elif interval.start < target_end:
                start += 1
            else:
                # interval.start > target_end
                if (mid - 1 < start) or (mid - 1 >= start and intervals[mid - 1].start < target_end):
                    return interval
                else:
                    end -= 1

        return None

Note:

• Time complexity = O(nlgn), n is the number of the elements in the given array.