There are n patients currently waiting to see the doctor. The ith patient requires an estimated consultation time of ti minutes, as determined by the triage. There is only one doctor, and the doctor can only serve a single patient at any point in time, and all other patients must wait. For example, if the ﬁrst patient that the doctor serves has ti = 5, the remaining n−1 patients must all wait for an additional 5 minutes. You may assume that once the doctor ﬁnishes serving a patient, he will immediately serve the next patient — any time in between serving two patients is negligible. The doctor can serve the patients in any order. The doctor must serve all patients. The doctor wishes to minimize the total waiting time of all patients. Describe the most eﬃcient algorithm you can think of to ﬁnd the minimum total waiting time required to serve all patients. What is the running time of your algorithm?
In the suggested answer, a greedy approach is used. All the patients are sorted by waiting time — O(N log N). Serve patients in increasing Ti — O(N). Total: O(N log N).
However, i was thinking that with the given constraints, to minimize the total waiting time will simply be serving the patient with the longest consultation last. Thus i will make one pass through n patients to find patient P with the longest consultation time. Make a second pass to perform rolling sum in order to determine the total waiting time, and when i encounter the patient P, i will skip this patient. This will take O(n).
May i know what’s wrong with this approach ?