2. You work at the emergency room at a hospital. Patients come in and you evalua

Question

2. You work at the emergency room at a hospital. Patients come in and you evaluate the severity of their injury by assigning a real number from 1 to 100. Whoever has the highest number (and in case of ties, whoever arrived first) sees the doctors first. When a doctor is available, no time should be wasted; you want to identify the person who goes next as quickly as possible (minimize the worst case) (a) How will you handle the data, to automate this process? b) How much time will it take to send the next patient to the doctors, assuming you've had time to set up properly? (c) How long will it take to reorganize after a patient is sent through to the doctors? (d) How long will it take to reorganize after a new patient arrives and you have evalu- ated their injury? e) Someone in the wait room gets worse, and you assign a new number for them. How do you reorganize and how long does it take? (f) Someone miraculously gets all better and leaves (after letting you know). How do you reorganize and how long does it take? (g) Now suppose that all of the assessment numbers are values that get rounded to the first decimal (e.g., 23.6, 63.9, 44.1, etc). How do you handle the data and how does it affect the time complexity of the above situations?

Explanation / Answer

1) I will form an max heap with injury as the sorting parameter.

2) Once the heap is setup the time to find the max injured patient is O(1) which will be the top element. So time will be O( 1 ).

3) Reordering in a heap will take O(lg n) time to keep the max heap property.

4) Adding a new patient is like adding a new element to heap which will take O(lg n) time.

5) We can do this by removing the patient whose priority is to be changed and then added again with new priority. Time for removing will be O(lg n) and time for ading new patient will be O(lg n). So overall time will be O(lg n).

6) We just have to remove that patient which will take O(lg n) time total to remove the patient and reorder.

7) It doesnt change the anything since the priorities are just used for comparing and nothing else so instead of intiger comparison we will be doing floating point comparison.

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.