Maximize Pages Before Suspension
Updated
Problem statement
The engineering team at an Amazon fulfillment center is tuning n high-performance printers. Printer i can print pages[i] pages and has a limit called threshold[i].
Each printer is always in exactly one of three states: operational, idle or suspended. All printers start idle. You turn them on one at a time, in any order you choose. A printer you turn on becomes operational and prints its pages[i] pages right away.
Suspension rule: let x be the number of operational printers right after you turn one on. Then every printer with threshold[i] <= x is suspended at once.
- The printer you just turned on still prints its pages first, even if it is suspended right after.
- Idle printers with
threshold[i] <= xare suspended too, so you can never turn them on. - Suspended printers stop printing and no longer count as operational.
For example, say two printers both have threshold 1 and print 3 and 9 pages. Turning on the 9-page printer makes 1 printer operational, so both printers are suspended. The best total is 9.
Return the largest total number of pages you can print.
Function
getMaxPages(pages: int[], threshold: int[]) → int
Complete the function getMaxPages in the editor.
getMaxPages has the following parameters:
int pages[n]: the number of pages each printer can printint threshold[n]: the threshold of each printer
Returns
int: the largest total number of pages you can print
Examples
Example 1
pages = [4, 1, 5, 2, 3]threshold = [3, 3, 2, 3, 3]return = 14Printers are numbered from 1. Turn on printer 4: it prints 2 pages. 1 printer is operational, and no threshold is 1 or less, so nothing is suspended. Turn on printer 3: it prints 5 pages. Now 2 printers are operational. Printer 3 has threshold 2, so it is suspended, and 1 printer stays operational. Turn on printer 1: it prints 4 pages. 2 printers are operational, and no printer left has threshold 2 or less. Turn on printer 5: it prints 3 pages. Now 3 printers are operational, so every printer with threshold 3 or less is suspended: printers 1, 4 and 5, and the idle printer 2. The total is 2 + 5 + 4 + 3 = 14. No order does better: of the four printers with threshold 3, at most 3 can print, and the best three give 4 + 3 + 2 = 9. Printer 3 adds 5. The answer is 14.
Example 2
pages = [2, 4, 4, 4, 5, 3]threshold = [1, 3, 1, 3, 3, 2]return = 20Printers are numbered from 1. Turn on printer 3: it prints 4 pages. 1 printer is operational, so printers 1 and 3 (both threshold 1) are suspended. Printer 1 was still idle. Now 0 printers are operational. Turn on printer 2: it prints 4 pages. 1 printer is operational, and nothing is suspended. Turn on printer 6: it prints 3 pages. Now 2 printers are operational, and printer 6 has threshold 2, so it is suspended. 1 printer (printer 2) stays operational. Turn on printer 4: it prints 4 pages, and 2 printers are operational. Turn on printer 5: it prints 5 pages. Now 3 printers are operational, so printers 2, 4 and 5 (threshold 3) are suspended. The total is 4 + 4 + 3 + 4 + 5 = 20. No order does better: only one printer with threshold 1 can print (at most 4 pages), printer 6 gives 3, and the three threshold 3 printers give 4 + 4 + 5 = 13. The answer is 20.
Example 3
pages = [2, 6, 10, 13]threshold = [2, 1, 1, 1]return = 15Printers are numbered from 1. Turn on printer 4: it prints 13 pages. 1 printer is operational, so every printer with threshold 1 is suspended: printers 2, 3 and 4. Printers 2 and 3 were still idle, so they can never print. Now 0 printers are operational. Turn on printer 1: it prints 2 pages. 1 printer is operational, and printer 1 has threshold 2, so it is not suspended. The total is 13 + 2 = 15. Only one of the threshold 1 printers can ever print, and 13 is the most of them. The answer is 15.
Constraints
1 <= n <= 10^5, wherenis the length ofpagesand ofthreshold1 <= pages[i] <= 10^41 <= threshold[i] <= n
More Amazon interview questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Maximal SquareONSITE INTERVIEW · Seen Nov 2026
- Serialize and Deserialize a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Diagonal Traversal of a Binary TreeONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
Similar questions at other companies
- IPO Share AllocationTwo Sigma · OATwo Sigma interview questions
- Initial Public OfferingPoint72 · OAPoint72 interview questions
- Catch Fish with Reusable BaitsSusquehanna International Group (SIG) · OASusquehanna International Group (SIG) interview questions
- Timed Task ManagementInstacart · ONSITE INTERVIEWInstacart interview questions
- Latest Arrival Time for a ShuttleGoogle · ONSITE INTERVIEWGoogle interview questions
- Experiment Bucket Allocation and RebalancingPinterest · PHONE SCREENPinterest interview questions
- Task Management SystemAirbnb · OAAirbnb interview questions
- Power Cell BankOptiver · OAOptiver interview questions
- Deployment Window SchedulerStripe · OAStripe interview questions
- Delete and Freeze GameRubrik · OARubrik interview questions