Java minheap solution


  • 0
    D
    public class Solution {
        public int[] findRightInterval(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) {
                return new int[0];
            }
            int n = intervals.length;
            Interval2[] intervals2 = new Interval2[n];
            for (int i = 0; i < n; i++) {
                intervals2[i] = new Interval2(i, intervals[i].start, intervals[i].end);
            }
            Arrays.sort(intervals2, new Comparator<Interval2>() {
                @Override
                public int compare(Interval2 i1, Interval2 i2) {
                    return i1.start - i2.start;
                }
            });
            Queue<Interval2> minheap = new PriorityQueue<Interval2>(1, new Comparator<Interval2>() {
                @Override
                public int compare(Interval2 i1, Interval2 i2) {
                    return i1.end - i2.end;
                }
            });
            int[] right = new int[n];
            for (int i = 0; i < n; i++) {
                Interval2 interval2 = intervals2[i];
                while (minheap.size() > 0 && minheap.peek().end <= interval2.start) {
                    right[minheap.poll().index] = interval2.index;
                }
                minheap.offer(interval2);
            }
            while (minheap.size() > 0) {
                right[minheap.poll().index] = -1;
            }
            return right;
        }
    
        class Interval2 {
            int index;
            int start;
            int end;
            Interval2(int index, int start, int end) {
                this.index = index;
                this.start = start;
                this.end = end;
            }
        }
    }
    

Log in to reply
 

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