题解 | #牛牛港#

题意整理

• 有n个工厂，提供了抵达时间和物资数量，由于每天只能装载一天，所以物资数量也相当于停留时间。
• 按先抵达的工厂先装载的规则，通过k个码头最少多少天完成装载任务。

方法一（排序+小顶堆）

1.解题思路

• 首先将工厂按抵达时间排好。
• 然后遍历所有工厂，如果某个工厂已经装载完毕，则从堆中移除。如果正在装载的工厂不足k个，说明还有空余的码头没有使用，直接将抵达时间+消耗时间放到堆里；如果达到k个，则需要等待堆顶的那个工厂装载完，将堆顶时间+消耗时间放到堆里，并且移除堆顶的工厂。
• 最后取出堆中最大的元素，即是最后一个工厂的装载结束时间。

动图展示：

2.代码实现

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) {
        //用于存放工厂id和抵达时间
        int[][] arr=new int[n][2];
        for(int i=0;i<n;i++){
            arr[i][0]=i;
            arr[i][1]=a[i];
        }
        //按抵达时间排序
        Arrays.sort(arr,(o1,o2)->o1[1]-o2[1]);

        //初始化小顶堆
        PriorityQueue<Long> queue=new PriorityQueue<>();
        for(int i=0;i<n;i++){
            int id=arr[i][0];
            //如果某个工厂已经装载完毕，则从堆中移除
            while(!queue.isEmpty()&&a[id]>=queue.peek()){
                queue.poll();
            }
            //如果正在装载的工厂不足k个，则直接将抵达时间+消耗时间放到堆里
            if(queue.size()<k){
                queue.offer((long)a[id]+b[id]);
            }
            //如果达到k个，则需要等待堆顶的那个工厂装载完
            else{
                queue.offer(queue.peek()+b[id]);
                queue.poll();
            }
        }

        //取出堆中最大的元素，即是最后一个工厂的装载结束时间
        while(queue.size()>1){
            queue.poll();
        }
        return queue.peek();

    }
}

3.复杂度分析

• 时间复杂度：最多n个工厂入堆，每次插入和删除的时间复杂度是，所以最终的时间复杂度是。
• 空间复杂度：需要额外大小为n的小顶堆，所以空间复杂度是。

方法二（TreeMap+小顶堆）

1.解题思路

• 首先初始化小顶堆，并将k个工厂预先放入堆。
• 然后初始化map，将抵达时间作为key，消耗时间作为value放入map，保证按抵达时间排好
• 遍历所有工厂，如果抵达时间大于等于某个工厂的结束任务时间，直接将抵达时间+消耗时间入堆；如果小于，则将堆顶时间+消耗时间入堆。
• 最后取出堆中最大的元素，即是最后一个工厂的装载结束时间。

2.代码实现

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) {
        //初始化小顶堆，并将k个工厂预先放入堆
        PriorityQueue<Long> queue=new PriorityQueue<>();
        for(int i=0;i<k;i++){
            queue.add(1L);
        }
        //初始化map，将抵达时间作为key，消耗时间作为value放入map
        TreeMap<Integer,Integer> map=new TreeMap<>();
        for(int i=0;i<n;i++){
            map.put(a[i],b[i]);
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            Integer day=entry.getKey();
            Integer duration=entry.getValue();
            Long poll=queue.poll();
            //如果抵达时间大于等于某个工厂的结束任务时间，直接将抵达时间+消耗时间入堆
            if(day>=poll){
                queue.add(Long.valueOf(day+duration));
            }
            //如果小于，则将堆顶时间+消耗时间入堆
            else{
                queue.add(poll+duration);
            }
        }
        //取出堆中最大的元素，即是最后一个工厂的装载结束时间
        while(queue.size()>1){
            queue.poll();
        }
        return queue.peek();
    }
}

3.复杂度分析

• 时间复杂度：最多n个工厂入堆，每次插入和删除的时间复杂度是，所以最终的时间复杂度是。
• 空间复杂度：需要额外大小为n的小顶堆和TreeMap，所以空间复杂度是。