Find the least wastage in cutting the Trees?

Problem
You are given n Trees with their heights in an array. and you are given a value k units , that much wood you need to collect. You can have an axe of any height you want but you can use only 1 axe when you choose.

Assume height to be integral value.

Solution

So, if height of the tree is H, and you cut it at height X from the ground then H-X will be used will be used. If there is only 1 tree, we will cut it at height X, such that H-X = k.

It is always possible to choose an axe height such that chopping all trees above this height will result in zero waste.
To see this, just sort the trees in descending order of height, and consider moving the axe height gradually down from the top of the tallest tree.

Suppose the tallest tree has height h. Notice that the function:

f(x) = total amount of wood cut by using an axe of height h - x to
       chop all trees of at least this height

• Sort the trees by their height in descending order
•  starts at 0 when x = 0, and is an increasing piecewise linear function of x, with no discontinuities. Every time x increases past the point when one or more trees just start to become choppable, the rate of change of f(x) increases, but this doesn't cause problems. 
• So for any desired level of wood y, just (conceptually) intersect a horizontal line of height y with the graph f(x), and drop a vertical line from this point down to the x axis to find its value. (How to actually do this in a program I leave as an exercise, but here's a hint: consider trees in decreasing height order to find the pair of adjacent x values x1, x2 such that chopping at h - x1 produces too little wood, and h - x2 produces too much.)

Reference

• http://stackoverflow.com/questions/18053325/algorithm-find-the-least-wastage-in-cutting-the-trees