Java easy PriorityQueue solution O(nlogn)


  • 0
    A
    public class Solution {
        public class MyInterval {
            int idx;
            int start;
            int end;
            public MyInterval(int i, int s, int e) { idx = i; start = s; end = e; }
        }
        public int[] findRightInterval(Interval[] intervals) {
            int len = intervals.length;
            MyInterval[] myintervals = new MyInterval[len];
            int[] re = new int[len];
            if(len==0)  return re;
            Arrays.fill(re, -1);
            PriorityQueue<MyInterval> pq = new PriorityQueue<>((a,b)->(a.end-b.end));
            for(int i=0; i<len; i++) 
                myintervals[i] = new MyInterval(i, intervals[i].start, intervals[i].end);
            Arrays.sort(myintervals, (a,b)->(a.start-b.start));
            int i = 0;
            while(i<len) {
                int cur = myintervals[i].start;
                pq.offer(myintervals[i]);
                i++;
                while(i<len && myintervals[i].start==cur)
                    pq.offer(myintervals[i++]);
                while(!pq.isEmpty() && i<len && pq.peek().end<=myintervals[i].start) {
                    re[pq.poll().idx] = myintervals[i].idx;
                }
            }
            return re;
        }
    }
    

Log in to reply
 

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