Maximum Saw Height for At Least M Cut Length
Problem statement
You have vertical wooden poles with integer heights heights. Set a saw to a non-negative integer height h; every pole taller than h contributes height - h units of wood, and shorter poles contribute nothing.
Given requiredWood, return the largest saw height that collects at least that much wood.
Function
maxSawHeight(heights: int[], requiredWood: int) → intExamples
Example 1
heights = [20,15,10,17]requiredWood = 7return = 15At height 15 the cuts yield 5 + 0 + 0 + 2 = 7. Raising the saw would yield too little.
Example 2
heights = [4,42,40,26,46]requiredWood = 20return = 36Height 36 yields 6 + 4 + 10 = 20 units from the three taller poles.
Example 3
heights = [5]requiredWood = 5return = 0The only way to collect all five units is to place the saw at ground level.
Constraints
1 <= heights.length <= 100000.1 <= heights[i] <= 10^9.1 <= requiredWood <= min(2 * 10^9, sum(heights)).