Last Updated: 10 Jun, 2022
Time to publish comic books
Moderate
Asked in company
Alice has decided to publish ‘X’ different comic books. For this purpose, he has ‘Y’ printing machines and ‘Z’ binding machines. The ‘ith’ printing machine takes ‘printMachine[i]’ minutes to print all pages of a comic book. Each binding machine takes ‘K’ minutes to bind all comic book pages.
At a single time, each machine(a printing or a binding) can process at most the pages of a single comic book.
For publishing a comic book, these steps have to be followed-
1. Start printing the pages of a comic book in an unoccupied ‘ith’ printing machine.
2. After ‘printMachine[i]' minutes, the printed pages are taken from the ‘ith’ printing machine.
3. After a non-negative amount of time, the printed pages of the comic book are placed in an unoccupied binding machine.
4. After ‘K’ minutes, the pages are removed from the binding machine.
Assume that the time is negligible for placing the pages into or removing them from the machines. You need to help Alice find the minimum time to publish X comics.
Example:
X=3, Y=2, Z=2, K=5
printMachine = [5, 7]
We can print the first book in the first printing machine at ‘T=0’, which takes five minutes. After that, we can give it to the first binding machine, which will bind it till ‘T=10’.
Similarly, we can print the second book in the second printing machine at ‘T=0’, which takes seven minutes. After that, we can give it to the second binding machine, which will bind it till ‘T=12’.
Hence, will finish both books in 12 minutes. So, the answer to this example will be 12.
Input Format
First-line contains 'T,' denoting the number of Test cases.
For each Test case:
The first line contains four integers ‘X’,’ Y’,’ Z’, and ‘K’
The second line contains ‘Y’ integers, the value for the ‘printMachine’ array.
Output format :
For each test case, print a single integer denoting the time taken to print all the books.
Print the output of each test case in a new line.
Constraints :
1 <= T <= 10
1 <= X <= 10^6
1 <= Y <= 10^5
1 <= Z <= 10^9
1 <= K <= 10^9
1 <= printMachine[i] <= 10^9
Time Limit: 1 sec
Approaches
Approach :
- We will maintain two minimum priority_queue, ‘printing’ and ‘binding’.
- ‘printing’ will store the time when any printing machine can complete a task if given.
- ‘binding’ will tell at what time binding machines will get free.
- Now, we will complete the books one by one. Give the book for printing to the machine, which will complete it the earliest. When it is printed, give it for binding to the free machine, which will get free the earliest.
- Maintain the status of every machine. We will maintain when it can deliver the printed book, and for binding, we will keep it when it is free.
- The answer to the problem is the time when we complete the binding of the last book.
Algorithm:
- Take two priority_queues, ’printing’ and ‘binding’.
- For every printing machine at ‘i’, push { print[i] , print[i] } in the printing queue. “ Every pair in the printing queue denote { the time it can deliver a printed book, the time it takes to print one book} “.
- For every binding machine, push 0 in the binding queue, denoting the time at which it is free. Initial every machine is free.
- For every ‘i’ book from 1 to ‘X’:
- Store the first machine from the printing queue in ‘printingMachine’ and delete it from the queue.
- I took the first machine from the binding queue in ‘bindingMachine’ and deleted it from the queue.
printingEndAt = printingMachine.first
timeToPrint = printingMachine.second
- Binding starts when both machines are free. Hence binding starts at the maximum of when printing ends or the binding machine is free. Binding ends at exactly the ‘K’ minutes after it has started.
bindingStartAt = max(printingEndAt, bindingMachine)
bindingEndAt = bindingStartAt + K
- Push {printingEndAt+timeToPrint, timeToPrint} in the printing. That is the next time when this machine can deliver any printed books. Also, push bindingEndAt in the binding queue.
- The answer to the problem will be the time when we bind the last book.