你能帮我设计一个算法并证明这个问题吗？
Could you help me design an algorithm and prove for this problem please?
我正在尝试找到作业中给出的此问题的算法：
Assume that you have m jobs and n machines. Each machine i has a
nondecreasing latency function li : N → R that only depends on the
number of jobs assigned to machine i. To illustrate, if lj(5) = 7,
then machine j needs to work 7 units of time if it is assigned (any)
five of the jobs. Assume that li(0) = 0 for all machines i.
Given a
set of m jobs, and n machines, where each machine is associated with a
nondecreasing latency function as described above. You are asked to
give a O(m · lgn) algorithm that assigns each job to a machine such
that the makespan(the maximum amount of time any machine executes) is
minimized. Needless to say, but just in case, you need to prove that
your algorithm is correct.
我可以得到一些帮助，所以这不是作弊。
我不知道从哪里以及如何开始寻找这个问题的算法，你能帮我吗？
O(m · lgn) 是很好的线索。
如何分配每个 m 个作业可能需要 O(logn) 时间？显然，机器应该以某种数据结构进行组织，每个操作都有所述时间。
考虑一下基于二叉堆的优先队列
我正在尝试找到作业中给出的此问题的算法：
Assume that you have m jobs and n machines. Each machine i has a nondecreasing latency function li : N → R that only depends on the number of jobs assigned to machine i. To illustrate, if lj(5) = 7, then machine j needs to work 7 units of time if it is assigned (any) five of the jobs. Assume that li(0) = 0 for all machines i.
Given a set of m jobs, and n machines, where each machine is associated with a nondecreasing latency function as described above. You are asked to give a O(m · lgn) algorithm that assigns each job to a machine such that the makespan(the maximum amount of time any machine executes) is minimized. Needless to say, but just in case, you need to prove that your algorithm is correct.
我可以得到一些帮助，所以这不是作弊。
我不知道从哪里以及如何开始寻找这个问题的算法，你能帮我吗？
O(m · lgn) 是很好的线索。
如何分配每个 m 个作业可能需要 O(logn) 时间？显然，机器应该以某种数据结构进行组织，每个操作都有所述时间。
考虑一下基于二叉堆的优先队列