We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Right Interval

Number: 436

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of intervals where each interval is represented as [start, end] and the start of each interval is unique, for each interval find the "right" interval. The "right" interval for an interval i is the interval j with the smallest start such that start_j is greater than or equal to end_i. If no such interval exists, return -1 for that interval.

Key Insights

  • Every interval’s start is unique, which enables mapping back to the original indices after sorting.
  • Sorting the intervals by their start value allows efficient searching.
  • Binary search can be used to quickly find the smallest start that is greater than or equal to a given end value.
  • The problem demands preserving the result order corresponding to the input order.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting and performing binary search for each interval. Space Complexity: O(n) for auxiliary data storage such as the sorted list of intervals and mapping between indices.

Solution

Sort the intervals based on their start values while keeping track of their original indices. For each interval in the original list, perform a binary search on the sorted list to find the smallest start that is greater than or equal to its end value. If such an interval is found, record its index; otherwise, record -1. This approach leverages sorting and binary search to efficiently find the right interval for each input interval.

Code Solutions

# Import bisect for binary search operations
import bisect

def findRightInterval(intervals):
    # Create a sorted list of tuples (start, original_index)
    sorted_starts = sorted((interval[0], i) for i, interval in enumerate(intervals))
    # Prepare a list of only the start values for binary search
    starts = [x[0] for x in sorted_starts]
    
    result = []
    # Process each interval in the original order
    for interval in intervals:
        end = interval[1]
        # Perform binary search to find leftmost start >= end
        index = bisect.bisect_left(starts, end)
        if index < len(starts):
            result.append(sorted_starts[index][1])
        else:
            result.append(-1)
    return result

# Example usage:
intervals = [[3,4],[2,3],[1,2]]
print(findRightInterval(intervals))  # Output: [-1, 0, 1]
← Back to All Questions