FastPrepFastPrep
Problem Brief

Maximize Pages Before Suspension

NEW GRADOA
See Amazon online assessment and hiring insights

The engineering team at an Amazon fulfillment center is optimizing their performance system where each printer can print pages/number of pages.

Each printer can be in exactly one of three states: operational, idle, or suspended.

  • Printers initially start in an idle state and can be activated one by one
  • However, all running printers cannot run at once, some will get suspended due to their threshold rules defined by the suspension rule

    • Suspension Rule: If there are at least x operational printers, all such printers i (with threshold[i] < x) will get suspended and stop printing.

    Task: The goal is to determine the maximum number of pages that can be printed before printers get suspended.

    Note:

  • Activating a printer with threshold[i] = x allows it to print pages[i] pages. However, once at least x printers are active, their pages gets printed first, and then all printers with threshold <= x will get suspended immediately
  • Choosing the activation order carefully is curcial to maximize the total printed pages before suspensions occur.

    • FastPrep extends its boundless thanks to the incredible friend who so generously shared the source! 🧡

    1Example 1

    Input
    pages = [4, 1, 5, 2, 3], threshold = [3, 3, 2, 3, 3]
    Output
    14
    Explanation
    The optimal way to maximize the number of pages printed is as follows (assuming 1-based indexing):
  • Turn on the 4th printer which prints 2 pages. Since the number of operational printers is 1 and it hasn't reached the threshold for any printer, no printer is suspended.
  • Next, turn on the 3rd printer which prints 5 pages. Now, there are 2 operational printers. Since the threshold for printer 3 is threshold[3] = 2, printer 3 gets suspended and stops functioning. So, now we have one printer which is the 4th printer.
  • Turn on the 1st printer which prints 4 pages. There are now 2 operational printers, and printer 1 remains functional as its threshold is threshold[1] = 3.
  • Finally, turn on the 5th printer which prints 3 pages. Now, there are 3 operational printers (printer 1, 4, and 5). Since all the remaining thresholds (1, 2, 4) are all less than or equal to 1, both printer 3 and printer 2 remain functioning.
    • Thus, the total number of pages printed is: 2 (from printer 4) + 5 (from printer 3) + 4 (from printer 1) + 3 (from printer 5) = 14 pages.

    2Example 2

    Input
    pages = [2, 4, 4, 4, 5, 3], threshold = [1, 3, 1, 3, 3, 2]
    Output
    20
    Explanation
    The optimal way to maximize the number of pages printed is as follows - (Assuming 1-based indexing :) 1. Turn on the 3rd printer, which prints 4 pages. At this point, since there are 1 operational printer and the thresholds for pinter 1 and 3 are 1, both printers 1 and 3 gets suspended and stop functioning. So, now we have 0 operational printer. 2. Next, turn on the 2nd printer, which prints 4 pages. No printers are suspended since the number of operational printers (equal to 1) is within the threshold. 3. Turn on the 6th printer, which prints 3 pages. Operational printers become equal to 2. Printer 6 gets suspended and stops working as its threshold is 2, and now there i only 1 operational printer (the 2nd one :( 4. Turn on the 4th printer, which prints 4 pages. Number of operational printers become equal to 2. 5. Finally, turn on the 5th printer, which prints 5 pages. Now printer 2, 4, and 5 gets suspended and stop working as there are 3 operational printers, and their threshold are less than or equal to 3. So, the total number of pages printed is -- 4 (from pinter 3) + 4 (from printer 2) + 3 (from printer 6) + 4 ... = 20

    3Example 3

    Input
    pages = [2, 6, 10, 13], threshold = [2, 1, 1, 1]
    Output
    15
    Explanation
    The optimal way to maximize the number of pages printed is as follows - (Assuming 1-based indexing :) 1. First, the engineers decide to activate the 4th printer, which prints 13 pages. At this point, the total number of operational printers is 1. The printing of 13 pages is completed first, followed by the suspension of any printers exceeding their threshold. 2. Next, since the threshold for printers 2, 3, and 4 is 1, and there is now 1 operational printer (4th printer), these printers become damaged. So, all the printers (2nd, 3rd, 4th) with threshold = 1, gets suspended and stop working. 3. Later, the only printer the team can turn on is printer 1. By activating printing 1, they print 2 more pages. The number of operational printer is now 1, and because threahold[1] = 2, printer 1 will not be suspended and remains functional. So, the total number of pages printed is 13 (from printer 4) + 2(from printer 1) = 15. we return 15.

    Constraints

    Limits and guarantees your solution can rely on.

    🐣
    public int getMaxPages(int[] pages, int[] threshold) {
  // write your code here
}
    Input

    pages

    [4, 1, 5, 2, 3]

    threshold

    [3, 3, 2, 3, 3]

    Output

    14

    Sign in to submit your solution.