小学生都能看懂的题解 | #主持人调度（二）#

问题解释

想象你有一堆活动，每个活动都有开始时间和结束时间。你需要为每个活动找一个主持人，但是同一个主持人在同一时间只能主持一个活动。我们想知道最少需要多少个主持人才能把所有活动都举办好。

解决方案步骤

1. 活动排序：首先，我们把所有活动按照开始时间从早到晚排列，这样就能更方便地检查每个活动。
2. 使用堆：我们用一个“优先队列”（可以想象成一个可以随时添加和删除的箱子），这个箱子里放的是正在进行的活动的结束时间。箱子里总是保持结束时间最早的活动在最上面。
3. 检查每个活动：
   • 对于每个活动，如果这个活动的开始时间大于或等于最上面的结束时间，说明这个活动可以用这个主持人，所以我们就把这个主持人（最上面的结束时间）拿掉，然后把当前活动的结束时间放进去。
   • 如果当前活动的开始时间小于最上面的结束时间，说明需要一个新主持人，所以我们把当前活动的结束时间也放进箱子里。
4. 最后结果：箱子里的活动结束时间的数量就是我们需要的主持人数。

代码解释

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class MinimumHostCount {
    public int minHostCount(int n, int[][] intervals) {
        if (n == 0) return 0; // 如果没有活动，返回0

        // 按开始时间排序活动
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

        // 创建一个最小堆，存储活动的结束时间
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int[] interval : intervals) {
            // 如果堆不为空且当前活动的开始时间 >= 堆顶的结束时间
            if (!minHeap.isEmpty() && interval[0] >= minHeap.peek()) {
                minHeap.poll(); // 移除堆顶的结束时间（复用主持人）
            }
            // 将当前活动的结束时间放入堆中
            minHeap.offer(interval[1]);
        }

        return minHeap.size(); // 返回堆的大小，代表需要的主持人数
    }

    
}

代码简要

• minHostCount 方法：这个方法用来计算需要多少个主持人。
• Arrays.sort：把活动按开始时间排好，方便后面处理。
• PriorityQueue：这个箱子用来管理结束时间。我们可以随时把结束时间放进去或拿出来。
• if 判断：检查当前活动是否可以使用之前的主持人，如果可以，就把它拿掉；否则就加一个新主持人。

希望这篇文章对你有帮助👍。