Find Right Interval

Find Right Interval

What is this problem about?

The Find Right Interval interview question is an interval-matching problem. You are given a set of intervals $[start_i, end_i]$. For each interval $i$, you need to find the "right interval" $j$ such that $start_j \geq end_i$ and $start_j$ is minimized. You should return an array of indices $j$, or -1 if no such interval exists.

Why is this asked in interviews?

Microsoft and Google use the Find Right Interval coding problem to assess your ability to use Binary Search on a custom dataset. It requires you to decouple the "index" from the "value" and sort the data to enable efficient searching. It tests your proficiency with Sorting interview patterns and searching for the "Lower Bound" of a value.

Algorithmic pattern used

This problem is solved using Sorting and Binary Search.

1. Store Original Indices: Since we need to return indices, create a list of pairs (start_time, original_index).
2. Sort: Sort this list based on the start_time.
3. Query: For each original interval's end_time:
   • Use binary search (specifically bisect_left or lower_bound) on the sorted start_time list to find the first interval whose start_time is $\geq$ current end_time.
   • If found, record its original index.

Example explanation

Intervals: [[3, 4], [2, 3], [1, 2]] (Indices: 0, 1, 2)

1. Start Map: (1, 2), (2, 1), (3, 0). Sorted by start.
2. Query interval 0 [3, 4]: Need start $\geq 4$. None. Result -1.
3. Query interval 1 [2, 3]: Need start $\geq 3$. Found (3, 0). Result 0.
4. Query interval 2 [1, 2]: Need start $\geq 2$. Found (2, 1). Result 1. Final Result: [-1, 0, 1].

Common mistakes candidates make

• Linear Search: Searching through all intervals for every query ($O(N^2)$), which will time out for large $N$.
• Sorting End Times: Trying to sort by end time, which doesn't help find the smallest start time $\geq$ a target.
• Losing Indices: Sorting the original intervals without keeping track of their initial positions.

Interview preparation tip

When you need to find the "smallest value $\geq$ X" in an array, your first thought should always be Sorting + Binary Search. It is the standard way to reduce a quadratic complexity to $O(N \log N)$.