Problem 1: Greedy Algorithm Suppose you have been selected to manage the total working time in one of the hospitals. Before being seen by a physician, a patient must be screened for COVID-19. The hospital has a single station for COVID-19 screening and n physicians to examine patients. Your task is to help treating/examining n patients in the shortest time possible. Each patient will have to go through two stages: screening time done at the COVID-19 station, and examining and treatment time done by the physicians. Let us say that patient Pi needs (si) minutes of time at the screening station, followed by (ei) minutes of time with the physician. Since there are at least n physicians available in the hospital, the examining time of the patients can be done fully in parallel where all patients can be examined at the same time. However, the screening station can only take one patient at a time, so your task will be to come up with an order in which the patients should be directed to the screening station. As soon as the first patient in order gets screened, he/she can be examined by one of the physicians; and the screening station can take the second patient. When the second patient completes the screening, he/she can proceed to one of the physician's office regardless of whether or not the first patient completes examination (since physicians work in parallel). Your task is to come up with an ordering of the patients at which all patients will complete examination at the earliest time possible. i. Give a polynomial-time algorithm that finds an optimal arrangement of taking patients with as small the completion time as possible. ii. Prove the correctness of your algorithm. Problem 1: Greedy Algorithm Suppose you have been selected to manage the total working time in one of the hospitals. Before being seen by a physician, a patient must be screened for COVID-19. The hospital has a single station for COVID-19 screening and n physicians to examine patients. Your task is to help treating/examining n patients in the shortest time possible. Each patient will have to go through two stages: screening time done at the COVID-19 station, and examining and treatment time done by the physicians. Let us say that patient Pi needs (si) minutes of time at the screening station, followed by (ei) minutes of time with the physician. Since there are at least n physicians available in the hospital, the examining time of the patients can be done fully in parallel where all patients can be examined at the same time. However, the screening station can only take one patient at a time, so your task will be to come up with an order in which the patients should be directed to the screening station. As soon as the first patient in order gets screened, he/she can be examined by one of the physicians; and the screening station can take the second patient. When the second patient completes the screening, he/she can proceed to one of the physician's office regardless of whether or not the first patient completes examination (since physicians work in parallel). Your task is to come up with an ordering of the patients at which all patients will complete examination at the earliest time possible. i. Give a polynomial-time algorithm that finds an optimal arrangement of taking patients with as small the completion time as possible. ii. Prove the correctness of your algorithm