A system is computing results for a set of different requests. Each request is answered by first querying a database, and then processing the query results to produce an answer. The system can process the query results in parallel (with one processor per request), but querying the database itself must be done sequentially (one request at a time).

Consider that we have an entire set of requests, and we can respond to them in any order we wish. We also have, for each request i, the time qi that will be needed to query the database and the time pi that will be needed to process the query results into the answer.

Processing this set of requests is monopolizing our system, so we would like to complete the entire process as soon as possible.

1. Design and write a greedy algorithm that, given the times qi and pi needed for each of n requests, will find the minimum time elapsed from the start of the first query until all requests have been answered.

2. Prove that your algorithm always finds an optimum result.