题解 | #主持人调度（二）#

package com.hhdd.贪心;

import java.util.*;

/**
 * 不会做
 *
 * @Author huanghedidi
 * @Date 2022/8/13 13:00
 */
public class 主持人调度2 {


    public static void main(String[] args) {
        int[][] startEnd = {{2147483646, 2147483647}, {2147483646, 2147483647}, {2147483646, 2147483647}, {2147483646, 2147483647}};
        int res = minmumNumberOfHost2(2, startEnd);
        System.out.println("res = " + res);
    }

    /**
     * 从最早开始到最晚开始遍历，找最大值
     * 确实想不到这种思路
     *
     * @param n
     * @param startEnd
     * @return
     */
    public static int minmumNumberOfHost(int n, int[][] startEnd) {
        // write code here
        int start1 = startEnd[0][0];
        int start2 = startEnd[0][0];
        for (int i = 1; i < startEnd.length; i++) {
            start1 = Math.min(startEnd[i][0], start1);
            start2 = Math.max(startEnd[i][0], start2);
        }
        int res = 0;
        for (int i = start1; i <= start2; i++) {
            int tmp = 0;
            for (int j = 0; j < startEnd.length; j++) {
                // 找出区间内的
                int[] item = startEnd[j];
                if (item[0] <= i && item[1] > i) {
                    tmp++;
                }
            }
            res = Math.max(res, tmp);
        }
        return res;
    }

    /**
     * 只会在边界的位置发生变化
     * 开始点增加 结束点减少
     * 最终结果取较大值
     * 需要额外的辅助空间
     *
     * @param n
     * @param startEnd
     * @return
     */
    public static int minmumNumberOfHost2(int n, int[][] startEnd) {
        // write code here
        // key 表示时点 value表示改时点需要几个主持人
        HashMap<Integer, Integer> help = new HashMap<>();

        for (int i = 0; i < startEnd.length; i++) {
            int[] item = startEnd[i];
            int start = item[0];
            int end = item[1];
            if (help.containsKey(start)) {
                help.put(start, help.get(start) + 1);
            } else {
                help.put(start, 1);
            }
            if (help.containsKey(end)) {
                help.put(end, help.get(end) - 1);
            } else {
                help.put(end, -1);
            }
        }
        Set<Integer> set = help.keySet();
        ArrayList<Integer> list = new ArrayList<>(set);
        Collections.sort(list);
        int res = 0;
        int sum = 0;
        for (Integer item : list) {
            sum += help.get(item);
            res = Math.max(res, sum);
        }
        return res;
    }

    /**
     * 使用优先队列解决（小根堆）
     * 优先队列的特点 有大小 且堆顶是最小值
     * 结合此题场景 什么时候需要新增主持人：前面所有的主持人都还在忙
     * 如果最早结束的主持人不在忙了，说明不需要新增主持人
     *
     * @param n
     * @param startEnd
     * @return
     */
    public static int minmumNumberOfHost3(int n, int[][] startEnd) {
        Arrays.sort(startEnd, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[1] - o2[1];
                }
            }
        });
        PriorityQueue<Integer> help = new PriorityQueue<>();
        for (int i = 0; i < startEnd.length; i++) {
            int[] item = startEnd[i];
            if (!help.isEmpty() && help.peek() <= item[0]) {
                help.poll();
            }
            help.offer(item[1]);
        }
        return help.size();
    }

}