Algorithms · Correctness proofs and asymptotic complexity
There are n jobs in fixed order with positive integer sizes s_1,…,s_n, and d≥1…
Problem
There are \(n\) jobs in fixed order with positive integer sizes \(s_1,\ldots,s_n\), and \(d\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(n\log S)\), where \(S=\sum_i s_i\). Prove the feasibility test and optimization correct, and state the result for \(d\ge n\).
Hint
** First test a proposed maximum load \(C\).
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
- Let all logarithms have base 2, and let all functions have domain the positive integersCorrectness proofs and asymptotic complexity
- Two disjoint color classes contain r≥1 red and b≥1 blue planar pointsDivide-and-conquer algorithms
- Using only comparisons, return both minimum and maximum among n≥1 distinct keysDivide-and-conquer algorithms
- Consider the invalid coding rule that repeatedly combines the two partial trees of…Greedy algorithms and exchange proofs
- The n vertices of a cycle are numbered 1,…,n, and vertex i has an integer weightGreedy algorithms and exchange proofs
- Given an undirected graph with up to five million vertices, produce exactly the…Dynamic programming and state design
- Prim’s algorithm starts at an arbitrary root and repeatedly adds a minimum-weight edge…Dynamic programming and state design
- Let T[0..n-1] be a text and P[0..m-1] a pattern over the same alphabet, where 1≤ m≤ nGraph optimization and traversal algorithms
- Consider SET COVER parameterized by the universe size p=|U|, while the number m of…Reductions, NP-completeness, and approximation