Loading page…
Practice problem · easy
A helpdesk app tags every support ticket with a category number. The team keeps a priority list of categories: the first category on the list is the most urgent.
You get the categories of the open tickets. Put them in the order the team wants to work. Tickets of a category on the priority list come first, in the order of that list, with all tickets of one category together. All other tickets follow, from the smallest category number to the largest.
Write order_by_priority(items, priority).
items[i] is the category of the i-th ticket. Categories can repeat.priority lists categories, most urgent first. The values in priority are all different, and some may not appear in items.Input: items = [7, 3, 9, 3, 5, 7, 1], priority = [3, 7]
Output: [3, 3, 7, 7, 1, 5, 9]Give every ticket a two-part key. A ticket on the priority list gets group 0 and its place in the list. Any other ticket gets group 1 and its own category number. Then sort by the key.
| Category | On the list? | Key |
|---|---|---|
| 7 | yes, place 1 | (0, 1) |
| 3 | yes, place 0 | (0, 0) |
| 9 | no | (1, 9) |
| 5 | no | (1, 5) |
| 1 | no | (1, 1) |
Sorted by key, the tickets read 3, 3, 7, 7, 1, 5, 9.
Input: items = [5, 3, 9, 3, 1], priority = [3]
Output: [3, 3, 1, 5, 9]Both tickets of category 3 come first. The rest are sorted: 1, 5, 9.
Input: items = [4, 1], priority = [4]
Output: [4, 1]Category 4 is on the list, so it goes first, even though 1 is smaller.
0 ≤ items.length ≤ 100,000 (tickets)0 ≤ priority.length ≤ 50,000 (categories)0 ≤ items[i], priority[j] ≤ 1,000,000priority are all different.For each priority category, scanning every ticket costs about n × m, which is 5 × 10^9 at n = 100,000 and m = 50,000. A table from category to place, and one sort on a two-part key, costs about n log n.
order_by_priority · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.