Time to publish comic books

Moderate
0/80
profile
Contributed by
0 upvote
Asked in company
Unthinkable Solutions

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 1 1 34
1100
2 3 2 10
10 16 1
Sample Output 1 :
2234
12
Explanation Of Sample Input 1 :
For test case 1:

X=2, Y=1, Z=1, K=34
printMachine = [1100]

We can print the first book in the first printing machine at ‘T=0’, which takes 1100 minutes. After that, we can give it to the first binding machine, which will bind it till ‘T=1134’.
We have to wait for 1100 minutes, then print the second book in the first printing machine at ‘T=1100’, which takes 1100 minutes. After that, we can give it to the binding machine, which will bind it till ‘T=2234’.
Hence, will finish both books by 2234 minutes. So, the answer to this example will be 2234.


For test case 2:

 X=2, Y=3, Z=2, K=10
printMachine = [10, 16, 1]

We can print the first book in the third printing machine at ‘T=0’, which takes a time of one minute. After that, we can give it to the first binding machine, which will bind it till ‘T=11’.
We have to wait for 1 minute, then print the second book in the third printing machine at ‘T=1’, which takes a time of one minute. 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.
Sample Input 2 :
2
4 3 2 15
3 5 7
5 2 5 100
10 10
Sample Output 2 :
35
130
Hint

Assign books to a printing machine that can complete them the earliest.

Approaches (1)
Priority Queue

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.
Time Complexity

O( X * (logY + log Z) ) where ‘X’ is the number of books we have to print, ‘Y’ is the number of printing machines we have, and ‘Z’ is the number of binding machines we have.

 

We are iterating over the number of books ‘X’, and for each book, we are inserting one element into both queues. 

Hence, time complexity will be O( X*(LogY + log Z) ).

Space Complexity

O( Y + Z ) where ‘X’ is the number of books we have to print and ‘Z’ is the number of binding machines we have.

 

We are maintaining two queues of size ‘Y’ and ‘Z’ respectively. 

Hence space complexity will be O(Y+Z).

Code Solution
(100% EXP penalty)
Time to publish comic books
Full screen
Console