堆的调度应用：任务调度与会议室

会议室 II（LeetCode 253）

最少需要多少个会议室（等价于同一时刻最多重叠会议数）：

public int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    // 小顶堆存各会议室的最早结束时间
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    for (int[] interval : intervals) {
        if (!minHeap.isEmpty() && minHeap.peek() <= interval[0]) {
            minHeap.poll();  // 最早结束的会议室可复用
        }
        minHeap.offer(interval[1]);
    }
    return minHeap.size();
}

差分数组 O(n) 方案（坐标离散化）：

public int minMeetingRooms(int[][] intervals) {
    TreeMap<Integer, Integer> diff = new TreeMap<>();
    for (int[] i : intervals) {
        diff.merge(i[0], 1, Integer::sum);
        diff.merge(i[1], -1, Integer::sum);
    }
    int max = 0, cur = 0;
    for (int v : diff.values()) { cur += v; max = Math.max(max, cur); }
    return max;
}

CPU 任务调度（LeetCode 621）

不同任务之间需要冷却时间 n，求执行所有任务的最短时间：

public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char t : tasks) freq[t - 'A']++;
    Arrays.sort(freq);
    int maxFreq = freq[25];
    int idleSlots = (maxFreq - 1) * n;
    // 其他任务先填冷却时隙
    for (int i = 24; i >= 0 && freq[i] > 0; i--) {
        idleSlots -= Math.min(freq[i], maxFreq - 1);
    }
    return tasks.length + Math.max(0, idleSlots);
}

贪心 + 大顶堆（模拟版，理解更直观）：

public int leastInterval(char[] tasks, int n) {
    int[] freq = new int[26];
    for (char t : tasks) freq[t - 'A']++;
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int f : freq) if (f > 0) maxHeap.offer(f);
    int time = 0;
    while (!maxHeap.isEmpty()) {
        List<Integer> temp = new ArrayList<>();
        int cycle = n + 1;  // 每轮执行 n+1 个任务槽
        while (cycle-- > 0 && !maxHeap.isEmpty()) {
            int f = maxHeap.poll() - 1;
            if (f > 0) temp.add(f);
            time++;
        }
        maxHeap.addAll(temp);
        if (!maxHeap.isEmpty()) time += cycle + 1;  // 补足冷却空闲
    }
    return time;
}

重构字符串（LeetCode 767）

任意相邻字母不同，若最多频次字母 > (n+1)/2 则不可能：

public String reorganizeString(String s) {
    int[] freq = new int[26];
    for (char c : s.toCharArray()) freq[c - 'A']++;
    PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[1] - a[1]);
    for (int i = 0; i < 26; i++) if (freq[i] > 0) maxHeap.offer(new int[]{i, freq[i]});
    StringBuilder sb = new StringBuilder();
    while (maxHeap.size() >= 2) {
        int[] a = maxHeap.poll(), b = maxHeap.poll();
        sb.append((char)('A' + a[0])).append((char)('A' + b[0]));
        if (--a[1] > 0) maxHeap.offer(a);
        if (--b[1] > 0) maxHeap.offer(b);
    }
    if (!maxHeap.isEmpty()) {
        int[] last = maxHeap.poll();
        if (last[1] > 1) return "";
        sb.append((char)('A' + last[0]));
    }
    return sb.toString();
}

总结