题解 | #牛牛港#

题目：
有k个港口，n个工厂，第i个工厂的抵达时间为 $a_{i}$ ,第i个工厂的货数量为 $b_{i}$ ,一个港口一天只能装一吨并且一次只能负责一个工厂，求将所有工厂装载完毕的最少时间

方法一：优先级队列

封装一个工厂类，其中包含工厂的编号和抵达时间，因为先到达的工厂先装载，所以工厂按照抵达时间放入最小堆中，定义另一个最小堆c模拟k个港口中每个工厂的装货时间
抵达时间早的工厂先出队，当下一个工厂抵达时间 $a[id]$ 大于等于 $c$ 堆顶工厂的装货时间，则不断将装载完毕的工厂出队,空出港口
如果工厂到达时有剩余港口，则当前工厂的装载时间=工厂抵达时间+装载吨数
如果工厂到达时没有剩余港口，则当前工厂装载时间=堆顶工厂装载结束时间+装载吨数，堆顶工厂装载结束后出队，空出港口
返回堆底工厂装载结束时间

图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型
     */
    class factory{
        int id,a;//工厂编号和工厂到达时间
        factory(int id,int a){
            this.id=id;
            this.a=a;
        }
    }
    public static Comparator fComparator = new Comparator<factory>(){
        public int compare(factory f1, factory f2) {
            return f1.a - f2.a;
        }
    };
    public long solve (int n, int k, int[] a, int[] b) {
        // write code here
        //将工厂按照到达时间放在最小堆中，早到达的放在前面
        PriorityQueue<factory>f=new PriorityQueue<>(fComparator);
        for(int i=0;i<n;i++){
            f.add(new factory(i,a[i]));
        }
        //最小堆模拟k个港口
        PriorityQueue<Long> c=new PriorityQueue<>();
        //遍历工厂
        for(int i=0;i<n;i++){
            int id=f.poll().id;//到达的工厂编号
            //下一个工厂到达时上一个工厂已经装载完则可以将上一个工厂从堆中移除
            while(!c.isEmpty()&&a[id]>=c.peek()){
                c.poll();
            }
            //港口还有剩余，则当前港口的装货时间=抵达时间+装载吨数
            if(c.size()<k){
                c.add((long)a[id]+b[id]);
            }
            //如果k个港口都被占用则等待栈顶那个工厂装载完，因此当前港口装货时间=堆顶时间+当前工厂装载吨数，堆顶工厂装载完后出队
            else{
                c.add(c.peek()+b[id]);
                c.poll();
            }
        }
        while(c.size()>1)c.poll();
        return c.peek();//堆底元素即最后一个工厂装载结束时间
    }
}

复杂度：
时间复杂度： $图片说明$ ，工厂加入最小堆的时间复杂度为 $图片说明$ ,第二个循环的时间复杂度也是 $图片说明$
空间复杂度： $O(n+k)$ ，堆f的大小不超过n，堆c的大小不超过k,

方法二：TreeMap+最小堆

用TreeMap存储工厂的到达时间和货物数量，TreeMap存储保证了工厂按照到达时间从小到大排序，我们仍然用最小堆c模拟k个港口，同方法一不同的是，这里从k个港口的视角下装载货物，每次都出队一个港口，如果当前工厂的到达时间大于等于出队港口的工厂的装载时间，说明港口有剩余（之前初始化港口未有工厂时为0L）或者工厂到达港口时上一个工厂已经装载结束，当前工厂的装载时间=到达时间+装载数量，否则，没有港口剩余时，当前工厂装载时间=堆顶工厂装载结束时间+装载数量

图片说明

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型一维数组 
     * @param b int整型一维数组 
     * @return long长整型
     */
    public long solve (int n, int k, int[] a, int[] b) {
        // write code here
        //将工厂按照到达时间和货物数量存储在最小堆中，早到达的放在前面
        TreeMap<Integer,Integer>map=new TreeMap<>();
        for(int i=0;i<n;i++){
            map.put(a[i],b[i]);
        }
        //初始化k个港口中工厂的装货时间
        PriorityQueue<Long>c=new PriorityQueue<>();
        for(int i=0;i<k;i++){
            c.add(0L);
        }
        //遍历工厂
        for(Map.Entry<Integer,Integer>entry:map.entrySet()){
            Integer day=entry.getKey();
            Integer nums=entry.getValue();
            Long poll=c.poll();//第一个港口开始工作
            //港口还有剩余或者当前工厂到达时上一个工厂已经装载完毕，则当前港口的装货时间=抵达时间+装载吨数
            if(day>=poll)c.add(Long.valueOf(day+nums));
            //如果k个港口都被占用则等待堆顶那个工厂装载完，因此当前港口装货时间=堆顶时间+当前工厂装载吨数，堆顶工厂装载完后出队
            else
                c.add(poll+nums);
        }
        while(c.size()>1)c.poll();
        return c.peek();//堆底元素即最后一个工厂装载结束时间
    }
}

复杂度：
时间复杂度：第一个循环的时间复杂度是 $O(n)$ ,第二个循环时间复杂度是 $图片说明$ 第三个循环的时间复杂度是 $图片说明$ ,因此总的时间复杂度为 $图片说明$
空间复杂度：map的大小不超过n,c的大小不超过k, $O(n+k)$