O(nlogn), just array, with sorting and scanning


  • 1
    A

    The idea is very simple:

    1. Use a wrapper to track each interval's position
    2. Build two wrapper arrays. One is sorted by start, and the other by end
    3. Loop through the array sorted by end, compare its end with the start of the other array to find the RIGHT one.

    The code is in C#.

    public class Solution 
    {
        public int[] FindRightInterval(Interval[] intervals) 
        {
            if(intervals == null || intervals.Length <= 1) return new int[] { -1 };
            
            Wapper[] sIntervals = new Wapper[intervals.Length];
            Wapper[] eIntervals = new Wapper[intervals.Length];
            for(int i = 0; i < intervals.Length; i++)
            {
                sIntervals[i] = new Wapper(intervals[i], i);
                eIntervals[i] = new Wapper(intervals[i], i);
            }
            Array.Sort(sIntervals, (x, y) => (x.Start).CompareTo(y.Start));
            Array.Sort(eIntervals, (x, y) => (x.End).CompareTo(y.End));
    
            int[] result = new int[intervals.Length];
            for(int i = 0; i < result.Length; i++) result[i] = -1;
            
            int sIndex = 0;
            for(int i = 0; i < eIntervals.Length; i++)
            {
                while(sIndex < sIntervals.Length && eIntervals[i].End > sIntervals[sIndex].Start) sIndex++;
                
                if(sIndex >= sIntervals.Length) break;
                else result[eIntervals[i].Position] = sIntervals[sIndex].Position;
            }
            
            return result;
        }
        
        class Wapper
        {
            Interval interval;
            internal int Position { get; set;}
            internal int Start { get { return interval.start; } }
            internal int End { get { return interval.end; } }
            
            internal Wapper(Interval interval, int position)
            {
                this.Position = position;
                this.interval = interval;
            }
        }
    }
    

  • 0
    P

    I guess the for loop with while inside would translate to O(n^2) in worst case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.