Find minimum possible height of the highest tower

Question

I have towers with height H = h1,h2,h3... and i have a cutting machine that only cuts each tower with a specific length A = a1,a2,a3.. and i have m cuts find the minimum possible height of the highest tower.

for ex- H = 1, 4, 9, 16, 25 and A = 1,2,3,4,5

m = 3 ( only 3 cuts )

the minimum possible height is 15 as after cuts the array looks like H = 1,4,9,12,15 ( after applying 0, 0 , 0, 1, 2 cuts respectively on towers)

What I tried : I recognised it as greedy problem (correct me if i am wrong) and i tried to sort the H array and with a simple approach tried to cut down first the maximum height till it no longer remains maximum and then found the new maximum and again applied the same steps, it's correct but it's too naive and taking huge amount of time for large values?

Time taking steps : finding maximum element each time O(N) and sorting is also not an option (every time).

Constraints for n are upto 10^5 and m are around 10^18.

Is there any better approach? Guide me!!

Answer 1

Questions of the form minimum .. of the maximum .. are generally approachable by the idea of a binary search. We can formulate an O(N*log(M)) solution for the given question by applying a binary search over the metric to optimize that is, minimum possible height of the highest tower. Sharing a pseudocode for the same:

start = 0, end = 10^18
while start < end:
    cuts_used = 0 // Number of cuts used till now
    mid = (start + end) / 2
    // Let's see if its possible to trim down all the towers such
    // that height of each tower <= mid
    for i in range(0,N):
        if H[i] > mid:
            // Calculate the number of cuts required to bring H[i]<= mid
            cuts_required = ceil(1.0 * (H[i] - mid) / A[i])
            cuts_used += cuts_required
    // After iterating over the towers
    if cuts_used > M:
        // We're exceeding the number of cuts, hence increase the tower height
        start = mid + 1
    else:
        // We still have some more cuts left, so let's cut more
        end = mid - 1

return start

start should be our optimal answer, since our condition is defined as while start < end. Consider the case wherein our range is, start = 1 and end = 2. The mid for the given case is [(1 + 2)/2] = 1.

• Now If 1 is indeed our optimal answer, then cuts_used when mid = 1 will be <= M and hence our alogirthm will move end to mid - 1 that is, 0. Hence the range will be start = 1, end = 0 and we'll stop looping. Clearly start will be our solution.

• Now for the other case when 2 is the solution, cuts_used for mid = 1 will be > M and hence our algorithm will move start to mid + 1 and the range will become start = 2 and end = 2 - causing us to stop looping.

In either of the cases, it's visible that start should be our optimal solution.

Also, please note for computing ceil((H[i] - mid) / A[i]), we must not carry out an integer division since we'll lose the floating point and hence ceil will not work as intended. Therefore, ceil(1.0 * (H[i] - mid) / A[i]) should be considered to typecast the result to float for the input for ceil.