Serve Support Tickets Most-Urgent-First With Arrival Tie-Breaks
Solve this ProblemA help desk receives a stream of events: a new ticket arrives (add, with an urgency score) or an agent asks for the next ticket to work on (serve). Tickets are numbered 1, 2, 3, … in order of arrival. Each serve must hand back the number of the most urgent waiting ticket — the highest score wins, and if several tickets share the top score, the one that arrived earliest wins. Serving an empty queue reports -1.
Return the ticket number reported by every serve, in order.
Keeping a sorted array works, but every insert and every removal from the front shifts the whole waiting list. A binary heap keeps only the one thing that matters — who is first — and repairs itself along a single path after each change.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ ops.length ≤ 100, and priorities.length equals ops.length - ◆
Each op is either "add" or "serve"; for a "serve", the matching priorities entry is ignored - ◆
-1000 ≤ priorities[i] ≤ 1000; a higher number means a more urgent ticket - ◆
Tickets are numbered 1, 2, 3, … in the order their "add" operations occur
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Keep the Waiting List Sorted by Hand
BruteKeep every waiting ticket in a plain array that is always sorted from most urgent to least urgent. A new ticket is inserted by scanning from the front until its slot is found (equal-priority tickets that arrived earlier stay in front, which gives the arrival tie-break for free), then shifting everything behind it over by one. Serving is simply removing the front element, which also shifts every remaining ticket forward. Correct, but each add and each serve can touch every ticket currently waiting.
O(n²)O(n)1class Solution {
2 public List<Integer> serveTickets(String[] ops, int[] priorities) {
3 List<int[]> waiting = new ArrayList<>();
4 List<Integer> served = new ArrayList<>();
5 int nextId = 1;
6 for (int i = 0; i < ops.length; i++) {
7 if (ops[i].equals("add")) {
8 int pos = 0;
9 while (pos < waiting.size() && waiting.get(pos)[0] >= priorities[i]) pos++;
10 waiting.add(pos, new int[]{priorities[i], nextId++});
11 } else if (waiting.isEmpty()) {
12 served.add(-1);
13 } else {
14 served.add(waiting.remove(0)[1]);
15 }
16 }
17 return served;
18 }
19}Optimal — Binary Heap Keyed by (Urgency, Arrival)
OptimalA binary heap keeps the single most important ticket at the root without keeping the rest in any particular order. Order tickets by a two-part key: higher priority first, and for equal priority the smaller arrival id first. Adding a ticket appends it at the bottom and sifts it up; serving removes the root, moves the last ticket into its place and sifts it down. Both touch only one root-to-leaf path, so each operation costs O(log n) no matter how many tickets are waiting.
O(n log n)O(n)1class Solution {
2 public List<Integer> serveTickets(String[] ops, int[] priorities) {
3 PriorityQueue<int[]> queue = new PriorityQueue<>(
4 (a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(a[1], b[1]));
5 List<Integer> served = new ArrayList<>();
6 int nextId = 1;
7 for (int i = 0; i < ops.length; i++) {
8 if (ops[i].equals("add")) {
9 queue.offer(new int[]{priorities[i], nextId++});
10 } else if (queue.isEmpty()) {
11 served.add(-1);
12 } else {
13 served.add(queue.poll()[1]);
14 }
15 }
16 return served;
17 }
18}