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

import java.util.*;

/**
 * NC147 主持人调度（二）
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算成功举办活动需要多少名主持人
     * @param n int整型 有n个活动
     * @param startEnd int整型二维数组 startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
     * @return int整型
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        // return solution1(n, startEnd);
        // return solution2(n, startEnd);
        return solution3(n, startEnd);
    }

    /**
     * 数组排序+小根堆+队列
     * @param n
     * @param startEnd
     * @return
     */
    private int solution1(int n, int[][] startEnd){
        // 测试用例溢出: 10,[[2147483646,2147483647],[-2147483648,-2147483647],[2147483646,2147483647],[-2147483648,-2147483647],[2147483646,2147483647],[-2147483648,-2147483647],[2147483646,2147483647],[-2147483648,-2147483647],[2147483646,2147483647],[-2147483648,-2147483647]]
//        Arrays.sort(startEnd, (o1, o2) -> {
//            if(o1[0] == o2[0]){
//                return o1[1]-o2[1];
//            }else{
//                return o1[0]-o2[0];
//            }
//        });

        Arrays.sort(startEnd, (o1, o2) -> {
            if(o1[0] == o2[0]){
                if(o1[1] > o2[1]){
                    return 1;
                }else if(o1[1] < o2[1]){
                    return -1;
                }else{
                    return 0;
                }
            }else{
                if(o1[0] > o2[0]){
                    return 1;
                }else{
                    return -1;
                }
            }
        });

        Queue<Host> freeList = new LinkedList<>();
        PriorityQueue<Host> workHeap = new PriorityQueue<>(Comparator.comparing(o -> o.endTime));

        int result = 0;
        int curTime,start,end;
        Host host;
        for(int[] act: startEnd){
            start = act[0];
            end = act[1];
            curTime = start;
            while(!workHeap.isEmpty() && workHeap.peek().endTime<=curTime){
                freeList.offer(workHeap.poll());
            }
            if(!freeList.isEmpty()){
                host = freeList.poll();
                host.endTime = end;
                workHeap.offer(host);
            }else{
                host = new Host(System.currentTimeMillis(), end);
                workHeap.offer(host);
                result = Math.max(result, workHeap.size());
            }
        }

        return result;
    }

    /**
     * 小根堆+队列
     * @param n
     * @param startEnd
     * @return
     */
    private int solution2(int n, int[][] startEnd){
        PriorityQueue<Act> actHeap = new PriorityQueue<>((o1, o2) -> {
            if(o1.start == o2.start){
                if(o1.end > o2.end){
                    return 1;
                }else if(o1.end < o2.end){
                    return -1;
                }else{
                    return 0;
                }
            }else{
                if(o1.start > o2.start){
                    return 1;
                }else{
                    return -1;
                }
            }
        });

        for(int[] act: startEnd){
            actHeap.offer(new Act(act[0], act[1]));
        }

        Queue<Host> freeList = new LinkedList<>();
        PriorityQueue<Host> workHeap = new PriorityQueue<>(Comparator.comparing(o -> o.endTime));

        int result = 0;
        long curTime,start,end;
        Act act;
        Host host;
        while(!actHeap.isEmpty()){
            act = actHeap.poll();
            start = act.start;
            end = act.end;
            curTime = start;
            while(!workHeap.isEmpty() && workHeap.peek().endTime<=curTime){
                freeList.offer(workHeap.poll());
            }
            if(!freeList.isEmpty()){
                host = freeList.poll();
                host.endTime = end;
                workHeap.offer(host);
            }else{
                host = new Host(System.currentTimeMillis(), end);
                workHeap.offer(host);
                result = Math.max(result, workHeap.size());
            }
        }

        return result;
    }

    /**
     * 小根堆
     * @param n
     * @param startEnd
     * @return
     */
    private int solution3(int n, int[][] startEnd){
        PriorityQueue<Act> actHeap = new PriorityQueue<>((o1, o2) -> {
            if(o1.start == o2.start){
                if(o1.end > o2.end){
                    return 1;
                }else if(o1.end < o2.end){
                    return -1;
                }else{
                    return 0;
                }
            }else{
                if(o1.start > o2.start){
                    return 1;
                }else{
                    return -1;
                }
            }
        });

        for(int[] act: startEnd){
            actHeap.offer(new Act(act[0], act[1]));
        }

        PriorityQueue<Long> workHeap = new PriorityQueue<>();

        long curTime,start,end;
        Act act;
        while(!actHeap.isEmpty()){
            act = actHeap.poll();
            start = act.start;
            end = act.end;
            curTime = start;
            if(workHeap.isEmpty()){
                workHeap.offer(end);
            }else{
                if(workHeap.peek() <= curTime){
                    workHeap.poll();
                }
                workHeap.offer(end);
            }
        }

        return workHeap.size();
    }

    /**
     * 主持人
     */
    private class Host {
        private long id;
        private long endTime;
        private Host(long id, long endTime){
            this.id = id;
            this.endTime = endTime;
        }
    }

    /**
     * 活动
     */
    private class Act {
        private long start;
        private long end;
        private Act(long start, long end){
            this.start = start;
            this.end = end;
        }
    }
}