Cheapest on-call cover: hints, no solution
Hard · Trees
A company arranges on-call cover over its binary reporting tree. Each employee has a cost, the amount paid if that person is put on call. The rota must be complete: every employee has to be covered, and an employee is covered when they are on call, or their direct manager is on call, or at least one of their direct reports is on call.
The tree is given in level order: the root first, then the children of each present node from left to right, with null standing for a missing child. Nodes below a missing child are not listed.
The input lists each employee's cost in that level-order layout. Return the smallest total cost of a set of on-call employees that covers everyone. An empty tree costs 0. The tree can have up to 2000 employees, so the work must be linear in the number of employees; trying every subset is not an option.
Examples
- Input
- costs = [5, 2, 2]
- Output
- 4
- Note
- Putting both direct reports on call covers themselves and, through them, the manager: 2 + 2 = 4, cheaper than the manager at 5.
- Input
- costs = [1, 9, 9, 9]
- Output
- 10
- Note
- The root covers both its reports for 1, but the employee below the left report also needs cover, which costs 9.
Constraints
- 0 <= number of employees <= 2000
- Costs are integers from 1 to 1000
- Work in time proportional to the number of employees
Hint 1: a nudge
For one employee, in how many different ways can they end up covered, and which of those choices affect the people above them?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.