You are given a list of intervals, where each interval has:

start_i, end_i

Your task:

For every interval, find the interval whose start point is the smallest value greater than or equal to the current interval’s end point.

If such an interval exists, return its index.
If not, return -1.

Example:

Input: intervals = [[1,2]]
Output: [-1]

Example:

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation:
Interval [1,2] → next start ≥ 2 is at index 1 (i.e., [2,3])
Interval [2,3] → next start ≥ 3 is at index 0 (i.e., [3,4])
Interval [3,4] → none → -1

Example:

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

---

Problem Understanding

Important details:

• You must return results in the original interval order
• Only interval starts matter for matching
• Matching condition: start_j >= end_i
• If multiple match, choose the one with minimum possible start
• Intervals may not be sorted

Brute force would require comparing each interval to all others, leading to:

O(n²) — too slow for large input

We need faster.

---

Logic Explained in Simple English

Best way to think about it:

1. Extract all interval starts along with their original indices
2. Sort these starts
3. For each interval:
   • Look at its end value
   • Use binary search to find the first start value that is ≥ end
4. Record the corresponding index or -1 if no such start exists

Why this works:

• Sorting allows efficient searching
• Binary search finds first valid candidate in O(log n)
• Total runtime becomes O(n log n)

This ensures correctness and efficiency.

---

Step-by-Step Approach

1. Create an array of pairs: (startValue, originalIndex)
2. Sort this array by startValue
3. Prepare result array of size n
4. For each original interval:
   • Let target = endValue
   • Binary search in sorted start list to find first start ≥ target
   • If found → result[i] = corresponding index
   • Else → result[i] = -1
5. Return result

---

Java Implementation

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;
        int[][] starts = new int[n][2]; 
        // [startValue, originalIndex]

        for (int i = 0; i < n; i++) {
            starts[i][0] = intervals[i][0];
            starts[i][1] = i;
        }

        Arrays.sort(starts, (a, b) -> Integer.compare(a[0], b[0]));

        int[] result = new int[n];

        for (int i = 0; i < n; i++) {
            int target = intervals[i][1];
            int idx = binarySearch(starts, target);
            result[i] = idx;
        }

        return result;
    }

    private int binarySearch(int[][] starts, int target) {
        int left = 0;
        int right = starts.length - 1;
        int answer = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (starts[mid][0] >= target) {
                answer = starts[mid][1];
                right = mid - 1; // try to find smaller start
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
}

---

Dry Run Example

Input:

intervals = [[3,4],[2,3],[1,2]]

Step 1 — Extract starts:

[(3,0), (2,1), (1,2)]

Step 2 — Sort by start value:

[(1,2), (2,1), (3,0)]

Step 3 — Process each interval:

Interval 0: [3,4]

target = 4
Binary search → no start ≥ 4
result[0] = -1

Interval 1: [2,3]

target = 3
Binary search → first start ≥ 3 is (3,0)
result[1] = 0

Interval 2: [1,2]

target = 2
Binary search → first start ≥ 2 is (2,1)
result[2] = 1

Final output:

[-1, 0, 1]

---

Time and Space Complexity

Time Complexity

O(n log n)

Sorting + n binary searches

Space Complexity

O(n)

To store sorted starts and output array

---

Common Mistakes and How to Avoid Them

Mistake 1: Comparing start to start or end to end

Proper condition:

start_j >= end_i

Mistake 2: Returning any start ≥ end, not the smallest

Must use binary search to find earliest valid start

Mistake 3: Losing original interval order

Store original index alongside start

Mistake 4: Doing nested loops

Leads to O(n²) time and TLE

Mistake 5: Incorrect binary search termination

Must return first valid candidate, not just any

---