114. Hospital Triage Priority Scheduling

Hospital Triage Priority Scheduling

Hospital Triage Priority Scheduling determines the treatment order of a patient in a hospital emergency room.

You are given a list of severity values where severities.get(i) represents the severity level of the patient who arrived at time index i.

In the extended version, you are also given a list gender where gender.get(i) is either "M" or "F" for the patient at index i.

Return the treatment order of the patient at index k.

Basic Version

A patient with higher severity is treated first.
If two patients have the same severity, the patient who arrived earlier is treated first.
Treatment order is 1-based.

Extended Version

A patient with higher severity is treated first.
If two patients have the same severity, a patient with gender "F" is treated before a patient with gender "M".
If both severity and gender are the same, the patient who arrived earlier is treated first.
Treatment order is 1-based.

Method Signatures

int treatmentOrder(List<Integer> severities, int k)

severities contains the severity of each patient in arrival order.
k is the index of the patient whose treatment order must be returned.
k is 0-index based.
The return value is the 1-based treatment order of patient k.

int treatmentOrderWithGenderPriority(List<Integer> severities, List<String> gender, int k)

severities contains the severity of each patient in arrival order.
gender contains one value per patient, and each value is either "M" or "F".
k is the index of the patient whose treatment order must be returned.
The return value is the 1-based treatment order of patient k.

Constraints

1 ≤ severities.size() ≤ 100000
1 ≤ severities.get(i) ≤ 1000000000
0 ≤ k < severities.size()
severities is never empty.
severities is never null.
For the extended version, gender.size() == severities.size().
For the extended version, each gender.get(i) is either "M" or "F".
For the extended version, gender is never null.

Examples

Example 1: Basic Version

Method call: treatmentOrder(severities = List.of(3, 1, 4, 4, 2), k = 2)

Treatment order:

index 2 with severity 4
index 3 with severity 4
index 0 with severity 3
index 4 with severity 2
index 1 with severity 1

Patient at index 2 is treated first.

Output: 1

Example 2: Extended Version

Method call: treatmentOrderWithGenderPriority(severities = List.of(3, 1, 4, 4, 2), gender = List.of("M", "F", "M", "F", "M"), k = 2)

Patients at indices 2 and 3 both have severity 4. Since severity is the same and "F" has priority over "M", index 3 is treated before index 2.

Treatment order:

index 3
index 2
index 0
index 4
index 1

Patient at index 2 is treated second.

Output: 2

Example 3: Single Patient

Method call: treatmentOrder(severities = List.of(7), k = 0)

There is only one patient, so that patient is treated first.

Output: 1

Example 4: Same Severity in Basic Version

Method call: treatmentOrder(severities = List.of(5, 5, 5, 5), k = 3)

All severities are equal, so earlier arrival has priority. Treatment order is index 0, index 1, index 2, index 3.

Output: 4

Example 5: Same Severity with Gender Priority

Method call: treatmentOrderWithGenderPriority(severities = List.of(9, 9, 9, 9), gender = List.of("M", "F", "M", "F"), k = 2)

All severities are equal. Female patients come first, and among equal gender values earlier arrival comes first. Treatment order is index 1, index 3, index 0, index 2.

Output: 4