Challenge: The Ticket Window

Lab Java Intermediate 20 points

People queue for concert tickets, each wanting some number of tickets. The window sells one ticket per turn: the person at the front buys one; if they still want more, they go to the back of the line. Print the names in the order people finish (get all their tickets). Use a queue.

Input

Line 1: n. Then n lines: name tickets (tickets ≥ 1), in queue order.

Output

The names in finishing order, separated by spaces.

Example

Input

3
Amy 2
Ben 1
Cal 3

Output

Ben Amy Cal

Sample input available Sample output available

Editor

Java

Hints

Store each person's index in an ArrayDeque used as a queue.

poll() the front person, sell one ticket, and offer() them back if they want more.

Solution explanation

Each ticket sold is one O(1) poll and maybe one O(1) offer, so the total is O(total tickets).

Show solution

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[] name = new String[n];
        int[] want = new int[n];
        ArrayDeque<Integer> line = new ArrayDeque<Integer>();
        for (int i = 0; i < n; i++) {
            name[i] = sc.next();
            want[i] = sc.nextInt();
            line.offer(i);
        }
        StringBuilder sb = new StringBuilder();
        while (!line.isEmpty()) {
            int p = line.poll();
            want[p]--;
            if (want[p] > 0) {
                line.offer(p);          // back of the line
            } else {
                if (sb.length() > 0) sb.append(' ');
                sb.append(name[p]);
            }
        }
        System.out.println(sb);
    }
}

Output

Answer