题意分析

• 有$nn$n个工厂需要向码头发送货物进行运输。题目会给出每个工厂的物资到达码头的时间和该工厂的物资数量。但是码头只有$kk$k个。每个码头需要一次承包一个工厂的全部物资的装载，一个码头一天只能装载一吨物资。问最少需要什么时候可以完成所有的装载任务。

思路分析

• 贪心。我们可以先知道，肯定是先到的先进行装载，所以我们需要先对每个工厂运送过来的货物按照到达时间先后进行排序，如果在有空闲码头的情况下，可以任意选择一个码头进行装载，但是如果当前这个工厂的物资到达码头了，但是现在所有的码头都正在处理自己之前收到的装载任务，没有码头是空闲的，那怎么办呢？肯定是先空闲的码头优先得到这个工厂的装载任务，这样就能最小化时间的浪费。也就是我们需要找到当前最早结束装载任务的码头的装载结束时间。这里我们可以用一个小根堆进行处理。

• 举例分析如下

C++版本

• 代码如下
  • 首先，我们先按照到达的时间进行排序，时间复杂度为$O\left(nlogn\right)O(nlogn)$O(nlogn),然后，我们在处理的过程中利用小根堆进行优化，每次小根堆的处理时间为$O\left(logn\right)O(logn)$O(logn),$nn$n次的处理时间为$O\left(nlogn\right)O(nlogn)$O(nlogn),所以总的时间复杂度为$O\left(nlogn\right)O(nlogn)$O(nlogn)
  • 在这个过程中需要存储每个工厂的货物的到达时间和货物的数量，所以空间复杂度为$O\left(n\right)O(n)$O(n)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @param b int整型vector 
     * @return long长整型
     */
    struct node{
        long long begin; // 物资抵达的时间
        long long num;  // 物资的数量
        // 重载小于运算符，让物资抵达时间前的在前面
        bool operator <(const node &b){
            return begin<b.begin;
        }
    }Node[100010];
    long long solve(int n, int k, vector<int>& a, vector<int>& b) {
        // write code here
        // 定义一个小根堆，存储的是码头装载任务结束的时间是哪一天
        priority_queue<long long, vector<long long>, greater<long long> > q;
        for(int i=0;i<n;i++){
            Node[i].begin=a[i];
            Node[i].num=b[i];
        }
        
        // 按抵达时间排序
        sort(Node,Node+n);
        
        // 前面k个工厂的物资一次放到1-k个码头
        for(int i=0;i<min(n,k);i++){
            q.push(Node[i].begin+Node[i].num-1);
        }
        
        for(int i=k;i<n;i++){
            node x=Node[i];
            // 如果当前工厂的物资抵达的时间晚于最早结束装载任务的码头，
            // 那么他到达的时候这个码头没有接到其他任务，可以接受这个工厂的物资
            if(x.begin>q.top()){
               q.pop();
               q.push(x.begin+x.num-1);
            }else{
                // 否则，要等到当前最早结束装载任务的码头装载完毕之后才能进行装载
                long long y=q.top();
                 q.pop();
                 q.push(y+x.num);
            }
        }
        
        long long lst;
        while(!q.empty()){
            lst=q.top();
            q.pop();
        }
        lst+=1;
        // 返回最后结束装载任务的码头的那一天的后一天
        return lst;
    }
};

Go语言版

• Go语言版需要注意的是如果想利用小根堆，需要我们自己重新实现一些相关的接口。其余的思路都是一样的。
• 代码如下
  • 首先，我们先按照到达的时间进行排序，时间复杂度为$O\left(nlogn\right)O(nlogn)$O(nlogn),然后，我们在处理的过程中利用小根堆进行优化，每次小根堆的处理时间为$O\left(logn\right)O(logn)$O(logn),$nn$n次的处理时间为$O\left(nlogn\right)O(nlogn)$O(nlogn),所以总的时间复杂度为$O\left(nlogn\right)O(nlogn)$O(nlogn)
  • 在这个过程中需要存储每个工厂的货物的到达时间和货物的数量，所以空间复杂度为$O\left(n\right)O(n)$O(n)

package main

import (
	"container/heap"
	"sort"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @param k int整型
 * @param a int整型一维数组
 * @param b int整型一维数组
 * @return long长整型
 */
type node struct {
    begin int64
    num int64
}


// 自己重新实现部分堆的接口，定义一个小根堆，存储的是码头装载任务结束的时间是哪一天
type Plan struct {
    days int64
}
type PlanHeap []*Plan
 
func (p *PlanHeap) Len() int {
    return len(*p)
}
 
func (p *PlanHeap) Less(i, j int) bool {
    return (*p)[i].days < (*p)[j].days
}
 
func (p *PlanHeap) Swap(i, j int) {
    (*p)[i] ,(*p)[j] = (*p)[j],(*p)[i]
}
 
func (p *PlanHeap) Push(x interface{}) {
    (*p) = append((*p),x.(*Plan))
}
 
func (p *PlanHeap) Pop() interface{} {
    plen := len(*p)
    tmp := (*p)[plen-1]
    (*p) = (*p)[:plen-1]
    return tmp
}





func solve( n int ,  k int ,  a []int ,  b []int ) int64 {
    // write code here
    days := make([]node, n)

    for i :=0; i < n; i++ {
        var x node
        x.begin = int64(a[i])
        x.num = int64(b[i])
		days[i] = x
    }

	// 先按照时间的先后顺序进行排序
	sort.Slice(days, func(i, j int) bool {
		return days[i].begin < days[j].begin
	})

	

	ports := &PlanHeap{}
    heap.Init(ports)
 
    for i := 0;i < k;i++{
        heap.Push(ports,&Plan{0})
    }
    for i := 0;i<n;i++ {
        tmp := heap.Pop(ports)
        // 如果当前工厂的物资抵达的时间早于最早结束装载任务的码头，
        //要等到当前最早结束装载任务的码头装载完毕之后才能进行装载
        if tmp.(*Plan).days > int64(days[i].begin){
            tmp.(*Plan).days += int64(days[i].num)
        }else{
           // 如果当前工厂的物资抵达的时间晚于最早结束装载任务的码头，
            // 那么他到达的时候这个码头没有接到其他任务，可以接受这个工厂的物资
            tmp.(*Plan).days = int64(days[i].begin)
            tmp.(*Plan).days += int64(days[i].num)
 
        }
        heap.Push(ports,tmp)
 
    }
    var bottom *Plan = &Plan{}
    for len(*ports) > 0{
        bottom = heap.Pop(ports).(*Plan)
    }
    ans := (*bottom).days
    return ans
}