TreeMap<start, index>. O(n*logn)


  • 1
    A

    The idea is simple. For each interval's end we need to find higher or equal start. We can use tree map to store as a key intervals' starts and as a value will the index of the interval. Time complexity is O(n*logn)

    public class Solution {
        public int[] findRightInterval(Interval[] intervals) {
            int n = intervals.length;
            if (n==0) return new int[0];
            
            TreeMap<Integer, Integer> starts = getStartsMap(intervals);
            
            int rights[] = new int[n];
            for (int i=0; i<n; i++) {
                int end = intervals[i].end;
                Map.Entry<Integer, Integer> entry = starts.ceilingEntry(end);
                if (entry==null) rights[i]=-1;
                else rights[i] = entry.getValue();
            }
            
            return rights;
        }
        
        public TreeMap<Integer, Integer> getStartsMap(Interval[] intervals) {
            TreeMap<Integer, Integer> starts = new TreeMap<>();
            
            for (int i=0; i<intervals.length; i++) {
                starts.put(intervals[i].start, i);
            }
            return starts;
        }
    }
    

Log in to reply
 

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