题解 | #牛牛港#

思路：

题目的主要信息：

• 一共k个码头，每个码头每天可卸货一吨，完成一艘船的任务后才能开始下一艘船
• 一共n艘货船，到达码头的时间记录在数组a(每艘船到达时间不一样），货物吨数记录在数组b（本题中可直接认为是卸货天数）
• 先抵达先卸货，问最少多少天卸完

方法一：小顶堆+排序
具体做法：
因为是先到先卸货，且没有卸完这艘船不能开启下一艘船，因此我们可以对船按照到达时间进行排序，然后分配给k个码头。分配的时候我们使用小顶堆，若是船到达的时候还有空码头，可以直接分配，入堆即可，若是船到达的时候没有空码头了，我们可以将其需要时间接到堆顶（即最小的一个），这样耗时可以最短。每艘船到达的时候需要检查是否有完成的码头，这样可以及时空出码头来。最后堆底的元素就是我们完成所有任务的时间，如下图显示：

class Solution {
public:
    long long solve(int n, int k, vector<int>& a, vector<int>& b) {
        vector<int> index(n);
        for(int i = 0; i < n; i++)
            index[i] = i; //数组a的编号
        //对index按照a数组的到达时间排序
        sort(index.begin(), index.end(), [&a](int x, int y){return a[x] < a[y];});
        priority_queue<long long, vector<long long>, greater<long long>> pq; //小顶堆记录时间
        for(int i = 0; i < n; i++){ //按时间顺序对每个工厂的货物
            while(!pq.empty() && a[index[i]] >= pq.top()) //完成卸货的出堆
                pq.pop();
            if(pq.size() < k) //若有空码头,把任务给空的码头,结束时间是到达天数+耗时天数
                pq.push(a[index[i]] + b[index[i]]);
            else{ //若没有空码头，
                pq.push(pq.top() + b[index[i]]); //接在最小的后面入队
                pq.pop();
            }
        }
        while(pq.size() > 1) //最后一个就是完成的总时间
            pq.pop();
        return pq.top();
    }
};

复杂度分析：

• 时间复杂度：，sort函数排序为，遍历模拟这个过程为，内循环总共才次，总后求总时间为，故总时间复杂度为，去掉低次幂就是上述结果
• 空间复杂度：，辅助数组index记录下标，以及模拟过程使用的优先队列

方法二：小顶堆+有序哈希
具体做法：
因为题目明确说到了每艘船到达时间不一样，互斥让我们想到了哈希表。于是，我们可以使用有序哈希对船到达的时间进行排序（依赖于红黑树），然后遍历哈希表就是按照时间遍历每个工厂的船的货物，再用方法一的小顶堆来模拟计算总共需要的时间。

class Solution {
public:
    long long solve(int n, int k, vector<int>& a, vector<int>& b) {
        map<int, int> mp;
        for(int i = 0; i < n; i++) //按照时间顺序构建有序哈希
            mp[a[i]] = b[i];
        priority_queue<long long, vector<long long>, greater<long long>> pq; //小顶堆记录时间
        for(auto iter = mp.begin(); iter != mp.end(); iter++){ //按时间顺序对每个工厂的货物
            while(!pq.empty() && iter->first >= pq.top()) //完成卸货的出堆
                pq.pop();
            if(pq.size() < k) //若有空码头,把任务给空的码头,结束时间是到达天数+耗时天数
                pq.push(iter->first + iter->second);
            else{ //若没有空码头，
                pq.push(pq.top() + iter->second); //接在最小的后面入队
                pq.pop();
            }
        }
        while(pq.size() > 1) //最后一个就是完成的总时间
            pq.pop();
        return pq.top();
    }
};

复杂度分析：

• 时间复杂度：，有序哈希插入一次为，遍历数组所有元素就是，遍历模拟这个过程为，内循环总共才次，总后求总时间为，故总时间复杂度为，去掉低次幂就是上述结果
• 空间复杂度：，哈希表的大小为数组a的大小，以及模拟过程使用的优先队列