Greedy Scheduler
InterviewTime limit1sMemory limit512 MB
Assign each queued customer to the free cashier with the smallest number, track busy times, and output the cashier for every customer.
- Level
Medium4 of 10
- Topics
- Heap, Simulation, Implementation
- Solved
- No attempts yet
Problem
A store has n cashiers numbered 1 through n, and c customers are waiting in a queue. The customer at the front of the queue is constantly assigned to the unoccupied cashier with the smallest number. Processing the shopping cart of the ith customer takes ti seconds.
Determine which cashier will process each customer's shopping cart.
Input
The first line contains two space-separated integers n and c (1 ≤ n ≤ c ≤ 1000). The second line contains c space-separated integers t1, ..., tc (1 ≤ ti ≤ 1,000). ti is the time required to process that customer's shopping cart.
Output
On a single line, output the c cashier numbers that process each customer, separated by spaces.