Museum Conservation Chambers
Minimize max sum-plus-max cost over at most k contiguous paired-array groups
A museum must process a row of artifacts in conservation chambers. The artifacts must stay in their original order: each used chamber receives one nonempty contiguous group, and the groups together contain every artifact exactly once.
For artifact i:
handling[i]is its handling time.stabilization[i]is its required stabilization time.
A chamber first stabilizes its entire group, taking the largest stabilization time among that group's artifacts. It then handles the artifacts one at a time, taking the sum of their handling times. Thus, a group's processing time is:
sum of handling times + maximum stabilization time
All used chambers start simultaneously. You may use at most chambers chambers, and unused chambers do not affect the finishing time.
Return the smallest possible time by which every artifact can finish processing.
Examples
Example 1
Input: handling = [3,2,4], stabilization = [5,1,3], chambers = 2 Output: 9
Assigning the first two artifacts together and the last artifact alone gives group times of 10 and 7. Neither cut using two chambers finishes sooner.
Example 2
Input: handling = [1,1,1], stabilization = [0,9,0], chambers = 3 Output: 10
Even with one chamber available per artifact, an artifact needing 9 units of stabilization and 1 unit of handling cannot finish before time 10. Processing each artifact separately achieves that time.
Example 3
Input: handling = [2,4,3], stabilization = [1,5,2], chambers = 1 Output: 14
With only one chamber, all artifacts belong to one group. Its time is the total handling time plus the largest stabilization time.
Constraints
- 1 <= handling.length <= 8000
- stabilization.length == handling.length
- 1 <= handling[i] <= 1000000
- 0 <= stabilization[i] <= 1000000
- 1 <= chambers <= handling.length
The intended solution takes O(n log U) time and O(1) auxiliary space, where U is the sum of handling times plus the maximum stabilization time. Integer arithmetic is sufficient; all possible answers are exactly representable by JavaScript Number.
Hints
Show hint 1Hint 1
If all artifacts can finish within a particular time limit, can they also finish within a larger limit?
Show hint 2Hint 2
For a fixed limit, extend the current group as far as possible before starting another chamber. Adding artifacts never decreases a group's processing time.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return one optimal partition as a list of inclusive ending indices?
- What changes if each chamber has the same additional startup delay?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem