Medical Procedures: Schedule Medical Procedures Respecting Dependencies and Resource Constraints
Interview Experience
Problem
A hospital needs to schedule n medical procedures. Each procedure has a duration, a required room type, and a list of prerequisite procedures that must complete first. Rooms of the same type are interchangeable. Find the minimum total makespan (finish time of the last procedure) using as many rooms as needed.
python
def schedule_procedures(
procedures: list[dict], # {id, duration, room_type, prerequisites: list[str]}
rooms: dict # {room_type: count}
) -> dict: # {procedure_id: start_time}
pass
Example:
procedures = [
{"id":"A", "duration":30, "room_type":"OR", "prerequisites":[]},
{"id":"B", "duration":20, "room_type":"ICU", "prerequisites":["A"]},
{"id":"C", "duration":15, "room_type":"OR", "prerequisites":[]}
]
rooms = {"OR": 1, "ICU": 1}
**Output**: {"A": 0, "C": 30, "B": 30} # A and C compete for OR; B waits for A
Follow-ups
- How do you detect cycles in the prerequisite graph?
- This is a generalization of job-shop scheduling — what makes it NP-hard in the general case?
- For a practical hospital with 20 procedures, what heuristic gives good results quickly?
- How would you handle emergencies that must preempt a scheduled procedure?
Full Details
Problem
A hospital needs to schedule n medical procedures. Each procedure has a duration, a required room type, and a list of prerequisite procedures that must complete first. Rooms of the same type are interchangeable. Find the minimum total makespan (finish time of the last procedure) using as many rooms as needed.
python
def schedule_procedures(
procedures: list[dict], # {id, duration, room_type, prerequisites: list[str]}
rooms: dict # {room_type: count}
) -> dict: # {procedure_id: start_time}
pass
Example:
procedures = [
{"id":"A", "duration":30, "room_type":"OR", "prerequisites":[]},
{"id":"B", "duration":20, "room_type":"ICU", "prerequisites":["A"]},
{"id":"C", "duration":15, "room_type":"OR", "prerequisites":[]}
]
rooms = {"OR": 1, "ICU": 1}
**Output**: {"A": 0, "C": 30, "B": 30} # A and C compete for OR; B waits for A
Follow-ups
- How do you detect cycles in the prerequisite graph?
- This is a generalization of job-shop scheduling — what makes it NP-hard in the general case?
- For a practical hospital with 20 procedures, what heuristic gives good results quickly?
- How would you handle emergencies that must preempt a scheduled procedure?
About This Question
This is a candidate experience report from a oscar health interview during the phone round.
It covers the following topics: Coding, Graph, Phone, Onsite .