Funcia
Lv.1countingqueuesimulation

Priority Printer

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

A printer prints more important documents first. Its queue holds the documents in the order of priorities, where priorities[i] (1 to 9, higher is more important) is the importance of document i. The printer repeats:

  1. Take the document at the front of the queue.
  2. If any document still in the queue has a higher priority, put the taken document at the back of the queue.
  3. Otherwise print it.

Return the position (1-based) at which the document initially at index location is printed.

Examples

prioritieslocationresult
[2, 1, 3, 2]21
[1, 1, 9, 1, 1, 1]05
[1, 2, 3, 2, 1]44

Example 3 — the print order is documents 2, 3, 1, 4, 0: after document 3 is printed the queue is 4, 0, 1, so documents 4 and 0 are moved to the back before document 1 is printed.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(priorities: int[], location: int) → int

Constraints

  • 1≤1 \le priorities.length ≤200,000\le 200{,}000
  • 1≤1 \le priorities[i] ≤9\le 9
  • 0≤0 \le location << priorities.length

Expected complexity

Time
O(N)
Space
O(N)

Examples

prioritieslocationExpected
[2,1,3,2]21
[1,1,9,1,1,1]05
[1,2,3,2,1]44

Hint

Hint

Moving a document to the back never changes the cyclic order of the remaining documents, so the queue is always the remaining documents in original order, rotated. Documents of priority 9 are printed in cyclic order from the current start, then the start moves to just after the last one printed, and so on down to priority 1: O(9N)O(9N) in total. Simulating the queue and scanning it for a more important document at every step is O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.