[LeetCode] Find Right Interval

Problem: You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.

The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.

Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.

Example:

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

Approach: We can apply brute force approach by comparing every interval with each other but it will take O(n^2) time. If you see we need to find start time efficiently so what we can do is we can sort the intervals based on the start time and then we can apply binary search for every end time. 

The problem is if we apply the sorting we will loose our original index so what we can do is we can take another 2D array which will contain the start times and the original index. Then we can sort this new array based on the start times. 

That's all! Please note that in the implementation I am using Tuple instead of 2D array.

Implementation in C#:

        public static int[] FindRightInterval(int[][] intervals)

        {

            Tuple<int, int>[] sortedIntervals = new Tuple<int, int>[intervals.Length];

            for (int i = 0; i < intervals.Length; ++i)

            {

                sortedIntervals[i] = new Tuple<int, int>(intervals[i][0], i);

            }

            Array.Sort(sortedIntervals, (sI1, sI2) =>

            {

                return sI1.Item1.CompareTo(sI2.Item1);

            });

            int[] result = new int[intervals.Length];

            for (int i = 0; i < intervals.Length; ++i)

            {

                result[i] = FindRightIntervalBinarySearch(intervals[i][1], sortedIntervals);

            }

            return result;

        }

        private static int FindRightIntervalBinarySearch(int value, Tuple<int, int>[] sortedIntervals)

        {

            if (sortedIntervals[sortedIntervals.Length - 1].Item1 < value)

            {

                return -1;

            }

            int start = 0, end = sortedIntervals.Length - 1;

            while(start <= end)

            {

                int mid = start + (end - start) / 2;

                if (sortedIntervals[mid].Item1 >= value)

                {

                    end = mid - 1;

                }

                else

                {

                    start = mid + 1;

                }

            }

            return sortedIntervals[start].Item2;

        }

Complexity: O(nlogn)