Java clear O(n logn) solution based on TreeMap


  • 38
    I
    public class Solution {
        public int[] findRightInterval(Interval[] intervals) {
            int[] result = new int[intervals.length];
            java.util.NavigableMap<Integer, Integer> intervalMap = new TreeMap<>();
            
            for (int i = 0; i < intervals.length; ++i) {
                intervalMap.put(intervals[i].start, i);    
            }
            
            for (int i = 0; i < intervals.length; ++i) {
                Map.Entry<Integer, Integer> entry = intervalMap.ceilingEntry(intervals[i].end);
                result[i] = (entry != null) ? entry.getValue() : -1;
            }
            
            return result;
        }
    }
    

  • 1

    @ivtoskov brilliant! I think you could use TreeMap<Integer, Integer> map = new TreeMap<>() instead, this is cleaner.


  • 12
    Q

    @ivtoskov @xietao0221 Amazing. I use TreeMap.cellingKey() instead of cellingEntry.

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

  • 0

    @quantumlaser my code is exactly like yours.


  • 2
    I

    @xietao0221 In this case probably yes, because java.util.NavigableMap is not imported. Yet in general you want to define your variables with the interface type and not with the actual implementation


  • 1
    I

    @quantumlaser Yes, that also works well, but I wanted to retrieve it once.


  • 0
    Z

    Awesome !!! Love you


  • 3
    V

    @ivtoskov
    @xietao0221
    Correct me if I am wrong.
    Given that, you are using a treemap, which derived from Map. if you put the same key with a different value it will replace the original one with the newer one. In such case, if you have case like
    [[4,6],[1,2],[4,8]]
    the correct answer should be
    [-1,0,-1]

    However, the answer you provide will give
    [-1,2,1]

    Because in the treeMap the [4,8] will store as 4->2 ,which replace the
    previously inserted [4,6] stored as 4->0 for the Map property.

    Anyway, you guys show me how to use treemap, still be a brilliant solution.

    Updated:
    Here attached my edited code which can fix this problem while passing all the test case.

    	 public int[] findRightInterval(Interval[] intervals) {
             TreeMap<Integer, PriorityQueue<Integer>> map = new TreeMap<>();
             int[] res = new int[intervals.length];
             for(int i=0;i<intervals.length;i++){ 
            	 if(map.get(intervals[i].start)==null){
            		 PriorityQueue<Integer> pq=new PriorityQueue<>();
            		 pq.add(i);
            		 map.put(intervals[i].start, pq);
            	 }
            	 else{
            		 map.get(intervals[i].start).add(i);
            	 }
             }
             for(int i=0;i<intervals.length;i++) {
                 Integer key = map.ceilingKey(intervals[i].end);
                 res[i] = key!=null ?map.get(key).peek() : -1;
             }
             return res;
         }
    

  • 0
    C
    This post is deleted!

  • 1

    Amazing use of TreeMap! I didn't think about TreeMap so I did the dirty work on my own.
    Compared with my solution, we can observe that TreeMap saved a lot of work as follows:
    Thank for your sharing!

    1.Sort: key is sorted by start "automatically"
    2.Satellite data: Meanwhile value is used to save original index as satellite
    3.Out-of-box successor API: ceilingEntry() return successor, particularly the least key >= the given key or null if there is no such key.

        public int[] findRightInterval(Interval[] ints) {
            if (ints.length == 0) return new int[0];
            
            // Sort intervals in start point and save original index
            int n = ints.length;
            Interval[] nints = Arrays.copyOf(ints, n);
            Arrays.sort(nints, Comparator.comparingInt(i -> i.start));
            Map<Integer, Integer> idx = new HashMap<>();
            for (int i = 0; i < ints.length; i++) idx.put(ints[i].start, i);
            
            int[] ret = new int[n];
            for (int i = 0; i < n; i++) {
                int l = 0, r = n - 1;
                while (l < r) { // Essentially, find closest start point to ints[i].end
                    int m = l + (r - l) / 2;
                    if (ints[i].end > nints[m].start) l = m + 1; // m is too small
                    else r = m; // m is larger or equal, so keep m (it's OK: l=r-1 -> m=l -> l=r)
                }
                ret[i] = (ints[i].end <= nints[l].start) ? idx.get(nints[l].start) : -1; /* l==r */
            }
            return ret;
        }
    

  • 0
    N

    @Vordin It is looking for the minimum start key value greater than any interval's end value.


  • 0

    @cdai

    Binary search is a reasonable starting point for problems where entries/objects' order matters.
    I used the priority queue with the same result, but not as elegant as the top post.


  • 1

    Naive Implementation.

        public int[] findRightInterval(Interval[] intervals) {
            int [] answer = new int [intervals.length];
            List<int[]> sortedIntervals = new ArrayList<>();
            
            for (int idx = 0; idx < intervals.length; idx ++)
    			sortedIntervals.add(new int[] { intervals [idx].start, idx });
            
            Collections.sort (sortedIntervals, new Comparator<int[]>() {
    			@Override
    			public int compare(int[] o1, int[] o2) {
    				return o1 [0] - o2 [0];
    			}
    		});
            
            for (int idx = 0; idx < intervals.length; idx ++) {
            	int search = intervals [idx].end;
            	int low = 0, high = sortedIntervals.size() - 1;
            	boolean found = false;
            	
            	int mid = -1;
            	while (low <= high) {
    				mid = (low + high) >>> 1;
    				if (sortedIntervals.get(mid)[0] > search)
    					high = mid - 1;
    				else if (sortedIntervals.get(mid)[0] < search)
    					low = mid + 1;
    				else {
    					answer[idx] = sortedIntervals.get(mid)[1];
    					found = true; break;
    				}
    			}
    
            	answer[idx] = (!found) ? (low < sortedIntervals.size() && high < sortedIntervals.size() ? sortedIntervals.get(low)[1] : -1) : answer[idx];
            }
            
    		return answer;
        }
    

  • 0
    J

    Here is mine, using TreeMap. I used treemap.higherKey(). Could have used ceilingKey instead.

    public class Solution {
        public int[] findRightInterval(Interval[] intervals) {
            int n = intervals.length; 
            int[] r = new int[n]; 
            if (n==0 || n==1) { 
                r[0] = -1;
                return r; 
            }
            
            TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>(); //starting point vs. interval index. 
            for (int i=0; i<n; i++) {
                Interval in = intervals[i]; 
                if (tm.get(in.start)==null) {
                    tm.put( in.start, i); 
                }
            }
            
            for (int i=0; i<n; i++) {
                Interval in = intervals[i]; 
                int e = in.end;
                e--; 
                if (tm.higherKey(e)!=null) {
                    int key = tm.higherKey(e); 
                    r[i] = tm.get(key); 
                }
                else {
                    r[i] = -1; 
                }
            }
            
            return r;    
        }
    }
    

  • 0
    C

    @cdai I like this solution!


Log in to reply
 

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