Find Right Interval

Share

Given a list of intervals, for each interval find the index of the minimum starting point interval that has a start >= current end. Return -1 if no right interval exists.

Example 1
Input: [[1,2]] → Output: [-1]
Example 2
Input: [[3,4],[2,3],[1,2]] → Output: [-1,0,1]

Solution Approach

Map each start point to its interval index. Sort start points. For each interval's end, binary search for the smallest start >= end.

  • Build a TreeMap: startPoint -> original index.
  • For each interval, use ceilingEntry(end) to find smallest start >= end.
  • If found, record that index; else -1.
Java
import java.util.*;

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < intervals.length; i++)
            map.put(intervals[i][0], i);
        int[] result = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            Map.Entry<Integer,Integer> entry = map.ceilingEntry(intervals[i][1]);
            result[i] = entry == null ? -1 : entry.getValue();
        }
        return result;
    }
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)