Java Heap with O(nlogn)


  • 0
    D

    I like to use PriorityQueue to resolve this kind of questions regarding Interval like Merge-Interval or Meeting Room II

    private class Comp implements Comparator<Interval> {
        @Override
        public int compare(Interval a, Interval b) {
            if (a.start - b.start != 0) return a.start - b.start;
            else return a.end- b.end;
        }
    }
    
    public int eraseOverlapIntervals(Interval[] intervals) {
        PriorityQueue<Interval> queue = new PriorityQueue<>(new Comp());
        for (Interval i : intervals) queue.offer(i);
        int ret = 0;
        Interval last = queue.poll();
        while(queue.isEmpty() == false) {
            Interval curr = queue.poll();
            if (last.end > curr.start) {
                ret++;
                if (last.end > curr.end) last.end = curr.end;
            } else {
                last = curr;
            }
        }
        return ret;
    }

Log in to reply
 

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