253. Meeting Rooms II

Question: https://leetcode.com/problems/meeting-rooms-ii/

Post: https://leetcode.com/problems/meeting-rooms-ii/discuss/1123144/a-note-for-difference-between-whileif-when-polling-min-heap

A standard Min-Heap solution for this question would, well, use a Min-Heap, however I noticed some differences in terms of how you do the polling.

The better Solution using if for polling Min-Heap. This one takes 6ms

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        PriorityQueue<Integer> minHeap = new PriorityQueue();
        
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });

        for(int i = 0; i < intervals.length; ++i) {
            if(!minHeap.isEmpty() && intervals[i][0] >= minHeap.peek())
                minHeap.poll();
            
            minHeap.add(intervals[i][1]);
        }
        
        return minHeap.size();
    }
}

The solution I came up using while for polling Min-Heap. This one takes 7ms

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        PriorityQueue<Integer> pq = new PriorityQueue();
        
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        
        int minimalRoom = 0;
        
        for (int[] interval: intervals) {            
            while (!pq.isEmpty() && interval[0] >= pq.peek()) {
                pq.poll();
            }
            
            pq.add(interval[1]);
            minimalRoom = Math.max(minimalRoom, pq.size());
        }
        
        return minimalRoom;
    }
}

As you can see the only difference is how we poll the min-heap each time when a free meeting room should be availble. The one using while tries to remove all meetings that have ended at a given time, and use a second variable to record the maximum size of the min-heap, which is the minimal number of room we need. While the one using if only remove the lastest meeting, and directly return the size of the heap as the answer.

Why is the one using if better? Well since removing all ended meeting doesn't really reduce the minimal number of rooms we need(that number is fixed for each set of input), we might as well just remove that ONE room that has ended, and use it to host the next meeting. This way the size of the heap is the answer.