Skip to main content

Algorithms · Correctness proofs and asymptotic complexity

There are n jobs in fixed order with positive integer sizes s₁,…,sₙ, and d ≥ 1…

Problem

Algorithms practice problem

There are nn jobs in fixed order with positive integer sizes s1,…,sns_1,\ldots,s_n, and d≥1d\ge1 identical days. Each nonempty day receives one contiguous job block; jobs cannot split and empty days are allowed. Find the minimum possible maximum daily load in O(nlog⁡S)O(n\log S), where S=∑isiS=\sum_i s_i. Prove the feasibility test and optimization correct, and state the result for d≥nd\ge n.

Hint

Hint

** First test a proposed maximum load CC.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

Create a free account to check your answer and see the solution. Create a free account.

More Algorithms practice problems

Back to Algorithms

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.