Find Right Interval

                                            
class Solution {
public:
    vector<int> findRightInterval(vector<vector<int>>& intervals) {
        map<int, int> startIdxMap;
        vector<int> res;

        for (int i = 0; i < intervals.size(); ++i) {
            startIdxMap[intervals[i][0]] = i;
        }

        for (auto interval : intervals) {
            auto it = startIdxMap.lower_bound(interval[1]);
            if (it == startIdxMap.end()) {
                res.push_back(-1);
            } else {
                res.push_back(it->second);
            }
        }

        return res;
    }
};

                                            
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int n = intervals.length;
        int[] res = new int[n];
        
        for (int i = 0; i < n; i++) {
            map.put(intervals[i][0], i);
        }
        
        for (int i = 0; i < n; i++) {
            Integer key = map.ceilingKey(intervals[i][1]);
            res[i] = (key != null) ? map.get(key) : -1; 
        }
        
        return res;
    }
}

                                            
class Solution(object):
    def findRightInterval(self, intervals):
        start_sorted = sorted([(interval[0], index) for index, interval in enumerate(intervals)])
        result = []
        for interval in intervals:
            target = interval[1]
            left, right = 0, len(start_sorted) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if start_sorted[mid][0] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            result.append(start_sorted[left][1] if left < len(start_sorted) else -1)
        return result

                                            
/**
 * Note: The returned array must be malloced, assume caller 
calls free().
 */
int* findRightInterval(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize){
    int* result = (int*)malloc(intervalsSize * sizeof(int));
    
    for(int i = 0; i < intervalsSize; i++) {
        int minIndex = -1;
        int minStart = INT_MAX;
        for(int j = 0; j < intervalsSize; j++) {
            if(intervals[j][0] >= intervals[i][1] && intervals[j][0] < minStart) {
                minIndex = j;
                minStart = intervals[j][0];
            }
        }
        result[i] = minIndex;
    }
    *returnSize = intervalsSize;
    return result;
}

                                            
public class Solution {
    public int[] FindRightInterval(int[][] intervals) {
        int[] result = new int[intervals.Length];
        SortedDictionary<int, int> map = new SortedDictionary<int, int>();

        for (int i = 0; i < intervals.Length; i++) {
            map[intervals[i][0]] = i;
        }

        foreach (var interval in intervals) {
            var end = interval[1];
            var entry = map.FirstOrDefault(x => x.Key >= end);
            result[Array.IndexOf(intervals, interval)] = entry.Equals(default(KeyValuePair<int,int>)) ? -1 : entry.Value;
        }

        return result;
    }
}

                                            
/**
 * @param {number[][]} intervals
 * @return {number[]}
 */
var findRightInterval = function(intervals) {
    const startPoints = intervals.map((interval, index) => [interval[0], index]);
    startPoints.sort((a, b) => a[0] - b[0]);
    
    return intervals.map(interval => {
        const target = interval[1];
        let left = 0;
        let right = startPoints.length - 1;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (startPoints[mid][0] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return startPoints[left][0] >= target ? startPoints[left][1] : -1;
    });
};

                                            
function findRightInterval(intervals: number[][]): number[] {
    const n = intervals.length;
    const result: number[] = [];

    const sortedIntervals = intervals.map((interval, index) => [interval[0], interval[1], index]).sort((a, b) => a[0] - b[0]);
    
    for (let i = 0; i < n; i++) {
        let left = 0;
        let right = n - 1;
        let ans = -1;

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (sortedIntervals[mid][0] >= intervals[i][1]) {
                ans = sortedIntervals[mid][2];
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        result.push(ans);
    }

    return result;
};

                                            
class Solution {
    /**
     * @param Integer[][] $intervals
     * @return Integer[]
     */
    function findRightInterval($intervals) {
        $n = count($intervals);
        $startMap = [];
        $result = [];

        foreach ($intervals as $key => $interval) {
            $startMap[$interval[0]] = $key;
        }

        ksort($startMap);

        foreach ($intervals as $interval) {
            $target = $interval[1];
            $found = false;
            foreach ($startMap as $start => $index) {
                if ($start >= $target) {
                    $result[] = $index;
                    $found = true;
                    break;
                }
            }
            if (!$found) {
                $result[] = -1;
            }
        }
        
        return $result;
    }
}

                                            
class Solution {
    func findRightInterval(_ intervals: [[Int]]) -> [Int] {
        var res = [Int]()
        var intervalDict = [Int: Int]()
        
        for (index, interval) in intervals.enumerated() {
            intervalDict[interval[0]] = index
        }
        
        let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
        
        for interval in intervals {
            var low = 0
            var high = sortedIntervals.count - 1
            var rightIndex = -1
            
            while low <= high {
                let mid = low + (high - low) / 2
                if sortedIntervals[mid][0] >= interval[1] {
                    rightIndex = intervalDict[sortedIntervals[mid][0]] ?? -1
                    high = mid - 1
                } else {
                    low = mid + 1
                }
            }
            
            res.append(rightIndex)
        }
        
        return res
    }
}

                                            
class Solution {
    fun findRightInterval(intervals: Array<IntArray>): IntArray {
        val n = intervals.size
        val result = IntArray(n) { -1 }
        val sortedIntervals = intervals.mapIndexed { index, interval -> Pair(interval[0], index) }
            .sortedBy { it.first }
        
        for (i in intervals.indices) {
            val end = intervals[i][1]
            var left = 0
            var right = n - 1
            while (left <= right) {
                val mid = left + (right - left) / 2
                if (sortedIntervals[mid].first == end) {
                    result[i] = sortedIntervals[mid].second
                    break
                } else if (sortedIntervals[mid].first < end) {
                    left = mid + 1
                } else {
                    result[i] = sortedIntervals[mid].second
                    right = mid - 1
                }
            }
        }
        
        return result
    }
}

                                            
func findRightInterval(intervals [][]int) []int {
    n := len(intervals)
    result := make([]int, n)
    intervalsMap := make(map[int]int)

    for i, interval := range intervals {
        intervalsMap[interval[0]] = i
    }

    starts := make([]int, n)
    for i, interval := range intervals {
        starts[i] = interval[0]
    }

    sort.Ints(starts)

    for i, interval := range intervals {
        end := interval[1]
        idx := sort.SearchInts(starts, end)
        if idx == n {
            result[i] = -1
        } else {
            result[i] = intervalsMap[starts[idx]]
        }
    }

    return result
}

                                            
object Solution {
    def findRightInterval(intervals: Array[Array[Int]]): Array[Int] = {
        var res = Array.fill(intervals.length)(-1)
        val sortedIntervals = intervals.zipWithIndex.sortBy(_._1.head)
        for (i <- 0 until intervals.length) {
            var left = 0
            var right = intervals.length - 1
            while (left <= right) {
                val mid = left + (right - left) / 2
                if (sortedIntervals(mid)._1.head >= intervals(i)(1)) {
                    res(i) = sortedIntervals(mid)._2
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            }
        }
        res
    }
}

To solve this coding challenge, we need to find the smallest interval starting point that is greater than or equal to the ending point of each given interval in an array. If such an interval does not exist, return -1 for that interval. The solution uses sorting and binary search for efficient interval searching.

Explanation:

Problem Understanding : Each interval
i

= [starti, endi] has a unique start point. For each interval, we need to find another interval
j

such that startj >= endi, and startj is the smallest possible value meeting this condition. If no such interval exists, we return -1.
Examples Breakdown :

Example 1:
intervals = [[1, 2]]

. Because there is only one interval, no right interval exists, and the output is
[-1]

.
Example 2:
intervals = [[3, 4], [2, 3], [1, 2]]

. Here:

For [3, 4], no interval starts at or after 4, so the result is -1.
For [2, 3], the interval [3, 4] (index 0) starts at 3 which is >= 3, so the result is 0.
For [1,2], the interval [2,3] (index 1) is the right interval starting at 2 which is the smallest start >= 2, so the result is 1.

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

. Here:

For [1,4], no interval starts at or after 4, so the result is -1.
For [2, 3], the interval [3,4] (index 2) starts at 3 which satisfies the requirement, so the result is 2.
For [3, 4], no interval starts at or after 4, so the result is -1.

Approach :

First, sort the intervals based on the start points while keeping track of their original indices.
For each interval, perform a binary search on the sorted start points to find the smallest start point greater than or equal to the end point of the current interval.
Append the original index of the found interval to the result list, or append -1 if no such interval is found.

Detailed Steps in Pseudocode:

Sort the intervals by start points with their indices :

Create a list of tuples containing (start_point, index).
Sort this list based on the start_point.

Initialize the result list :

Create an empty list to store results.

Binary search for each interval's right interval :

For each interval in the input intervals,
Define the target as the end point of the current interval.
Using binary search, determine the smallest start point in the sorted list that is greater than or equal to the target.

Initialize binary search bounds:
left

to 0,
right

to the length of sorted list - 1.
While
left

is less than or equal to
right

:

Compute mid-point.
If sorted[mid].start is less than target, adjust
left

.
Otherwise, adjust
right

.

After the loop, check if the index
left

is within bounds.

If true, append the index of that start point to result.
Otherwise, append -1.

Return the result list .

The pseudocode implementation along with comments explaining each step is as follows:

                                            
# Pseudocode function to find right intervals

# Function definition
function findRightInterval(intervals):
    # Step 1: Sort intervals based on start points
    start_sorted = sort([(interval[0], index) for index, interval in enumerate(intervals)]) 
    # 'start_sorted' is a list of tuples (start_point, original_index)
    
    result = [] # Initialize result list
    
    # Step 2: Binary search for each interval
    for interval in intervals:
        target = interval[1]  # End point of the current interval
        left = 0  # Initialize binary search bounds
        right = length(start_sorted) - 1
        
        # Binary search loop
        while left <= right:
            mid = left + (right - left) // 2
            if start_sorted[mid][0] < target: # If mid start point is less than target
                left = mid + 1  # Move left bound up
            else: # If mid start point is greater than or equal to target
                right = mid - 1  # Move right bound down
        
        # After binary search, check if we found valid interval
        if left < length(start_sorted):
            result.append(start_sorted[left][1]) # Append found interval's original index
        else:
            result.append(-1) # Append -1 if no interval found
    
    return result # Return the list of results

In this solution, sorting the intervals by their starting points and using binary search helps efficiently find the right intervals with a time complexity of O(n log n) due to sorting and searching operations, where

n

is the number of intervals.

Keep in mind that topics like sorting algorithms, binary search, and tuple handling must be clearly understood to grasp the complete functionality of this solution. This method ensures computational efficiency, making the approach suitable for handling large data sets as specified in the constraints.