【优先级队列】主持人调度（二）

求解代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public int minmumNumberOfHost (int n, int[][] startEnd) {
        Arrays.sort(startEnd,(a,b)->{
            if(a[0]==b[0]){
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(a[0], b[0]);
        });

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int maxHost = 0;
        for(int[] activity:startEnd){
            while(!queue.isEmpty()&&queue.peek()<=activity[0]){
                queue.poll();
            }

            queue.offer(activity[1]);
            maxHost = Math.max(maxHost,queue.size());
        }
        return maxHost;
    }

踩坑记录

❌1.排序比较器整数溢出

1
2
3


Arrays.sort(startEnd, (a, b) ->
    (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0])
);

❌2.返回值不能返回最后的堆大小

1

return queue.size(); //

因为题目要的是整个过程中，堆出现过的最大大小。

❌3.释放主持人只用 if可能不够

1
2
3


if (queue.peek() <= activity[0]) {
    queue.poll();
}

因为实际情况下可能有多个活动已经结束。