Cutting Wood

This problem involves optimizing resource allocation, a common theme in software engineering. It tests your ability to apply binary search in a non-traditional way to find the optimal solution within a defined range.

binary searchoptimizationresource allocationarrays

Problem Statement

A local farm collective needs to harvest crops from a set of fields. Each field yields a different amount of produce, represented by an array of non-negative integers. The collective wants to set a minimum harvest yield target: any field yielding less than this target is skipped. Given the array of field yields and a required total harvest amount, determine the highest possible minimum yield target that still allows the collective to meet or exceed their harvest requirement. Assume it's always possible to meet the harvest requirement with a target of 0.

Example 1

Input: field_yields = [10, 4, 8, 6, 12], required_harvest = 30

Output: 6

A minimum yield target of 6 results in harvesting from fields with yields 10, 8, 6, and 12, totaling 10 + 8 + 6 + 12 = 36, which meets the required harvest. A target of 7 would only harvest from 10, 8, and 12, totaling 30, which also works, but 6 is the highest such value. A target of 8 only harvests from 10, 8, and 12 totaling 30. A target of 9 only harvests from 10 and 12, totaling 22, which is less than 30. A target of 6 yields 10 + 8 + 6 + 12 = 36, which is still greater than 30. Therefore 6 is the highest minimum target.

Example 2

Input: field_yields = [5, 5, 5, 5], required_harvest = 20

Output: 5

A minimum yield target of 5 results in harvesting from all fields, totaling 20, which meets the required harvest. Any target higher than 5 would result in harvesting less than 20. For example, a target of 6 results in harvesting nothing.

Constraints

-1 <= number of fields <= 10^5
-0 <= field yield <= 10^9
-0 <= required harvest <= sum of all field yields
-Field yields are non-negative integers.

Brute Force Approach

The most straightforward approach is to try every possible minimum yield target, starting from 0 up to the maximum yield of any field. For each target, calculate the total harvest and check if it meets the requirement. Like trying different combinations on a lock until you find the right one, this is inefficient. This approach involves iterating through all possible yield targets and, for each target, iterating through all fields.

TimeO(n*m)

SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem