Problem 1 (10 points) A developer has a project to build a large number n of houses. Each house's building requirements are dierent. House i has digging time di for the foundations, and building time 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, the developer employs enough workers, they can start working on each house once the foundations have been dug out, working on as many houses simultaneously as needed. The goal is to nish the whole project in the smallest amount of time. Give an algorithm to decide the optimal order of digging the 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)?]

Problem 1 (10 points) A developer has a project to build a large number n of houses. Each house's building requirements are different. House i has digging time di for the foundations, and building time 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, the developer employs enough workers, they can start working on each house once the foundations have been dug out, working on as many houses simultaneously as needed. The goal is to finish the whole project in the smallest amount of time. Give an algorithm to decide the optimal order of digging the 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)?] Problem 1 (10 points) A developer has a project to build a large number n of houses. Each house's building requirements are different. House i has digging time di for the foundations, and building time 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, the developer employs enough workers, they can start working on each house once the foundations have been dug out, working on as many houses simultaneously as needed. The goal is to finish the whole project in the smallest amount of time. Give an algorithm to decide the optimal order of digging the 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)?]