Find Right Interval - Leetcode Solution

Problem Statement:

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 interval j is on the "right" of interval 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.

Example:

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

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.

Solution:

We can solve this problem by applying the concept of Binary Search for each interval. Firstly, we will sort the given intervals based on their start points. Then, for each interval i, we will find the right interval which has the minimum start point such that its start point is greater than or equal to the end point of interval i. We can apply binary search for this purpose using the sorted intervals.

Algorithm:

1. Sort the intervals based on their start points.

2. For each interval i,

   a. Implement binary search to find the right interval j.

   b. If the right interval j exists, then store its index. Else, store -1.

Time Complexity: O(n log n) (Due to Sorting and Binary Search)

Space Complexity: O(n)

Here is the Python implementation of the above algorithm:

class Solution: def findRightInterval(self, intervals: List[List[int]]) -> List[int]: sorted_intervals = sorted([(x, i) for i, x in enumerate(intervals)], key=lambda x: x[0][0]) n = len(intervals) result = [-1] * n

    def binary_search(x):
        left, right = 0, n-1
        while left <= right:
            mid = (left+right) // 2
            if sorted_intervals[mid][0][0] >= x:
                right = mid - 1
            else:
                left = mid + 1
        if left == n:
            return -1
        return sorted_intervals[left][1]
    
    for i in range(n):
        end_point = intervals[i][1]
        j = binary_search(end_point)
        result[i] = j
        
    return result

We have defined a function binary_search that performs binary search on the sorted intervals to find the right interval for an interval i. We have used a helper function to sort the intervals based on their start points and also to store the index of each interval in the sorted intervals list. We have used a result list to store the index of the right interval for each interval i.

Finally, we iterate through all the intervals and find their right interval using the binary search function. We return the result list at the end.

1