If building a min heap is O(n), can my solution be O(n) time?


  • 0
    L
    public int eraseOverlapIntervals(Interval[] intervals) {
            if (intervals.length == 0) {
                return 0;
            }
            // the following part is to build the min heap. I employed default constructor 
            // for simplicity, which ends up with O(nlogn). But still, it is possible to build it in O(n)
            // though it costs O(n) space instead of O(1) while we sort the array
            PriorityQueue<Interval> minHeap = new PriorityQueue<>(intervals.length, new Comparator<Interval> () {
                @Override
                public int compare(Interval a, Interval b) {
                    return a.start - b.start;
                }
            });
            for (int i = 0 ; i < intervals.length ; i ++) {
                minHeap.offer(intervals[i]);
            }
            
            int end = Integer.MIN_VALUE;
            int count = 0;
            while (!minHeap.isEmpty()) {
                Interval top = minHeap.peek();
                if (end <= top.start) {
                    count ++;
                }
                if (end <= top.start || end > top.end) {
                    end = top.end;
                }
                minHeap.poll();
            }
            return intervals.length - count;
        }

  • 2
    C

    @LeoM58 Removing elements from a min-heap is an O(logn) operation, which you do O(n) times. So your algorithm will be O(n*logn).


Log in to reply
 

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