Untitled

import java.util.*;

public class Solution {
    public int[] findRightInterval(int[][] intervals) {
        int n = intervals.length;

        // Create an array of intervals with their original indices
        int[][] indexedIntervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            indexedIntervals[i][0] = intervals[i][0]; // start time
            indexedIntervals[i][1] = i;              // original index
        }

        // Sort intervals based on start times
        Arrays.sort(indexedIntervals, (a, b) -> Integer.compare(a[0], b[0]));

        int[] result = new int[n];

        // Iterate through each interval to find the right interval
        for (int i = 0; i < n; i++) {
            int end = intervals[i][1]; // end time of the current interval
            int idx = binarySearch(indexedIntervals, end);
            result[i] = idx == -1 ? -1 : indexedIntervals[idx][1]; // Add the original index of the found interval
        }

        return result;
    }

    // Binary search to find the smallest start time >= end time
    private int binarySearch(int[][] intervals, int target) {
        int left = 0, right = intervals.length - 1;
        int result = -1;

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

            if (intervals[mid][0] >= target) {
                result = mid; // Possible candidate
                right = mid - 1; // Search for smaller start time
            } else {
                left = mid + 1;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[][] intervals1 = {{1, 2}};
        System.out.println(Arrays.toString(solution.findRightInterval(intervals1))); // Output: [-1]

        int[][] intervals2 = {{3, 4}, {2, 3}, {1, 2}};
        System.out.println(Arrays.toString(solution.findRightInterval(intervals2))); // Output: [-1, 0, 1]
    }
}