algoadvance

You are given a collection of intervals represented as a list of lists, where each interval is a list [start, end]. For each interval, you need to find the smallest interval in the collection that starts after the end of this interval. Specifically, for each interval i, find an interval j such that intervals[i][1] <= intervals[j][0] and intervals[j][0] is the smallest possible value. If no such interval exists, the answer for that interval is -1.

Return an array of indices representing the answer for each interval. If there is more than one correct answer, you can return any of them.

Example:

intervals = [[1, 2], [2, 3], [3, 4]]
Output: [-1, 2, -1]

Constraints:

Strategy

  1. Collect Start Points:
    • Create a list of tuples containing the start point and their respective index.
  2. Sort the Start Points:
    • Sort this list by the start points. This will allow us to efficiently find the smallest starting interval that is greater than or equal to the end of the current interval.
  3. Binary Search:
    • For each interval, use binary search to find the first starting point that is greater than or equal to the end of the current interval.
  4. Construct Result:
    • Store the index of the found interval or -1 if no such interval exists.

Clarifying Questions

  1. What can we assume regarding the intervals? Are they always in sorted order?
    • We can assume they are not necessarily in sorted order.
  2. Is the length of the interval always greater than one?
    • Yes, each interval contains exactly two values indicating [start, end].
  3. Is there a particular preference for the returned index when multiple valid intervals are available?
    • No preference, any valid index can be returned.

Code

Here’s the Python implementation:

from bisect import bisect_left

def findRightInterval(intervals):
    start_points = sorted((start, i) for i, (start, end) in enumerate(intervals))
    n = len(intervals)
    result = [-1] * n  # To store the results

    for i, (start, end) in enumerate(intervals):
        # Find the first interval whose start is >= the end of the current interval
        idx = bisect_left(start_points, (end,))
        if idx < n:
            result[i] = start_points[idx][1]
    
    return result

# Example usage:
intervals = [[1, 2], [2, 3], [3, 4]]
print(findRightInterval(intervals))  # Output: [-1, 2, -1]

Time Complexity

  1. Sorting: Sorting the start_points will take O(n log n), where n is the number of intervals.
  2. Searching: We perform a binary search for each interval which will take O(log n). Since we do this for each of the n intervals, the total cost for searching is O(n log n).

Thus, the overall time complexity is O(n log n).

This approach ensures efficient handling of the problem within the given constraints.

Try our interview co-pilot at AlgoAdvance.com