Problem 547566 · hard · Phase 05 Advanced Algorithms & Graphs

Walk-In Clinic Dispatcher

gauntlet · simulation · scheduling · priority rules

A walk-in clinic has doctors doctors numbered 0 .. doctors-1, all free at minute 0. patients is a list of tuples (name, arrival, severity, duration, patience). Simulate the clinic one minute at a time, starting at minute 0, until every patient has either started treatment or walked out. At each minute t, perform these steps in this exact order:

  1. Finish. A treatment that started at minute s with duration d finishes at minute s + d. At that minute its doctor becomes free, unless it was that doctor's 3rd, 6th, 9th, ... finished treatment: then the doctor rests and becomes free at minute t + 2 instead. A doctor who becomes free in step 1 can be assigned in step 5 of the same minute.
  2. Arrive. Every patient whose arrival == t enters the waiting room.
  3. Escalate. For every patient in the waiting room let w = t - arrival. If w is a positive multiple of 5, that patient's severity goes up by 1, but never above 5. The new severity is kept from then on.
  4. Walk out. Every waiting patient whose current severity is at most 2 and whose w >= patience leaves the clinic untreated.
  5. Assign. Go through the waiting patients in priority order: higher current severity first, then earlier arrival, then earlier position in patients. For each one:
    • If no doctor is free, step 5 ends.
    • A patient with duration > 6 is a long case. When doctors >= 2, a long case may only be assigned if at least two doctors are free at that moment; otherwise the patient is skipped (stays waiting) and the next patient in the order is considered. With a single doctor there is no such restriction.
    • Otherwise the patient is assigned to the free doctor whose treatments started so far have the smallest total duration (ties: smaller doctor number). The treatment starts at minute t and the patient leaves the waiting room.

Return the list of events in the order they happen: (name, doctor, t) when a patient starts treatment and (name, -1, t) when a patient walks out. Within one minute, walk-outs come first (in the order the patients appear in patients), then assignments in the order step 5 makes them.

Examples

Input:  doctors = 1
        patients = [("Ann", 0, 2, 3, 10), ("Bo", 1, 4, 2, 10), ("Cy", 1, 1, 2, 4)]
Output: [("Ann", 0, 0), ("Bo", 0, 3), ("Cy", -1, 5)]
Explanation: Ann is treated from minute 0 to 3. At minute 3 Bo (severity 4)
goes before Cy. At minute 5 the doctor is free again, but Cy has waited
4 minutes, has patience 4 and severity 1, so Cy walks out in step 4,
before step 5 could assign Cy.

Input:  doctors = 2
        patients = [("Dee", 0, 3, 4, 0), ("Eli", 0, 3, 2, 0), ("Fay", 1, 5, 8, 0), ("Gus", 2, 2, 1, 9)]
Output: [("Dee", 0, 0), ("Eli", 1, 0), ("Gus", 1, 2), ("Fay", 1, 4)]
Explanation: Fay is a long case. At minutes 2 and 3 only one doctor is free,
so Fay is skipped and Gus is treated instead. At minute 4 both doctors are
free; doctor 0 has started 4 minutes of treatment and doctor 1 only 3, so
Fay goes to doctor 1.

Constraints

  • 1 <= doctors <= 5
  • 0 <= len(patients) <= 300; names are distinct non-empty strings
  • 0 <= arrival <= 500, 1 <= severity <= 5, 1 <= duration <= 20, 0 <= patience <= 100

Goals

  • Simulate a system minute by minute with a fixed order of steps
  • Apply several interacting priority and tie-break rules exactly
  • Track per-doctor state such as rest periods and accumulated workload
Starting Python…