Challenge: Emergency Room

Lab Java Intermediate 20 points

Commands arrive: arrive name level (a higher level is more urgent) or treat. On treat, print the name of the patient to see now: the highest level; if levels tie, whoever arrived first. If nobody is waiting, print nobody.

Input

Line 1: q. Then q commands.

Output

One line per treat.

Example

Input

7
arrive Ana 3
arrive Raj 5
arrive Li 5
treat
treat
arrive Max 9
treat

Output

Raj
Li
Max

Sample input available Sample output available

Editor

Java

Hints

Store an arrival number with each patient to break ties.

The Comparator: compare levels (bigger first), then arrival (smaller first). poll() returns null when empty.

Solution explanation

Each arrive and treat is O(log n). A PriorityQueue is not stable on its own – the arrival number makes ties fair.

Show solution

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Patient {
    String name;
    int level, arrival;
    Patient(String name, int level, int arrival) { this.name = name; this.level = level; this.arrival = arrival; }
}

class Urgency implements Comparator<Patient> {
    public int compare(Patient a, Patient b) {
        if (a.level != b.level) return Integer.compare(b.level, a.level);   // higher level first
        return Integer.compare(a.arrival, b.arrival);                      // then earlier arrival
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        PriorityQueue<Patient> waiting = new PriorityQueue<Patient>(new Urgency());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < q; i++) {
            String cmd = sc.next();
            if (cmd.equals("arrive")) {
                waiting.offer(new Patient(sc.next(), sc.nextInt(), i));
            } else {
                Patient p = waiting.poll();
                sb.append(p == null ? "nobody" : p.name).append('\n');
            }
        }
        System.out.print(sb);
    }
}

Output

Answer