A developer has a project to build a large number n of houses. Each house'sbuilding requirements are dierent. House i has digging time di for the foundations, and buildingtime bi for building the house after the foundations have been dug out. Excavators are expensive, so there is only one: the foundations have to be dug out in some order. On the other hand, thedeveloper employs enough workers, they can start working on each house once the foundations havebeen dug out, working on as many houses simultaneously as needed. The goal is to nish the wholeproject in the smallest amount of time. Give an algorithm to decide the optimal order of diggingthe foundations. [Hint: Say the foundations of building 2 are dug just before those of building 3.How would the total completion time change if the order is changed from (2; 3) to (3; 2)?]

Answer explained below

Explanation:

Since we have to calculate the optimal time for digging only , keeping in mind that the building work has to be finished as soon as possible so the foundation with the minimum digging time has to be dug out first.

Hence it is needed to arrange the digging times of all the foundations in ascending order so that the building of the houses can be started as soon as possible.

So we apply the sorting algorithm here:(best sorting algorithm - quick sort)

/* l -- start index , h-- end index , p -- partition index */ quicksort(found[] , l , h) if( l < h) { p= partition( found, l , h); quicksort(found, l , p-1); // Before p quicksort(found , p+1 , h); // After p

/*partition() : This function takes the last element as pivot , places it at its correct position and put the larger elements at its right and smaller ones at its left */

partition(found[ ] , l , h) // pivot ( Element to be placed at right position) pivot = found[ h ];

i = l -1;

for( j = l ; j <= h -1 ; j++) { if ( found [ j ] < pivot )    

{ i++: //increment of smaller element

swap found [ i ] and found [ j ]

}

}

swap found [ i +1] and found [ h ]

return ( i+1)

}

/* The sorted array found [ ] gives the order in which the foundations are to be dug out in order to get the work done in the minimum time possible.*/