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

• ``````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;
}``````

• @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).

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