The engineering team at an Amazon fulfillment cent...

Idea → reduce to classic “job-sequencing-with-deadlines”

What the rules really mean	Programming translation
• When k printers have been activated so far, the next printer we start must have threshold > k.	Each printer i must be scheduled no later than slot threshold[i] − 1 (0-based).
• After that activation we have k + 1 operational printers, so all printers whose threshold ≤ k are “suspended forever” (and can never be started).<br>⇒ In every time-slot we may start at most one printer.	We can perform at most one “job” per slot.

So every printer is a job

• profit * = pages[i]
• deadline * = threshold[i] − 1 (latest slot in which it can be activated).

Maximising pages printed before any suspension is exactly the classical problem:

“Pick the most profitable subset of jobs so that no more than one job is done in each time-slot ≤ its deadline.”

---

Optimal algorithm ( O(n log n) )

1. Build pairs (pages, deadline) with deadline = threshold − 1.
2. Sort the pairs in descending order of pages.
3. Keep a disjoint-set-union (union-find) structure recording the latest free slot ≤ s.
   • find(s) returns the rightmost still-empty slot ≤ s, or −1 if none.
4. Traverse the pairs:
   • slot = find(deadline).
   • If slot ≥ 0, take it: add pages to the answer and mark that slot as used by union(slot, slot–1).

Because every printer is considered exactly once and each union-find operation is inverse-Ackermann time, the whole run-time is O(n log n) for the initial sort plus near-linear afterwards; memory O(n).

---

Reference implementation

cpp
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) {            // returns right-most free slot ≤ x
        if (x < 0) return -1;
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void occupy(int x) {         // mark slot x as used
        parent[x] = find(x - 1);
    }
};

long long getPages(vector<int>& pages, vector<int>& threshold) {
    const int n = pages.size();
    vector<pair<int,int>> jobs;           // {pages, deadline}
    jobs.reserve(n);
    for (int i = 0; i < n; ++i)
        jobs.emplace_back(pages[i], threshold[i] - 1);

    sort(jobs.begin(), jobs.end(),
         [](const auto& a, const auto& b){ return a.first > b.first; });

    DSU dsu(n);                            // slots 0 … n-1
    long long total = 0;
    for (auto [pg, dl] : jobs) {
        int slot = dsu.find(dl);
        if (slot >= 0) {
            total += pg;
            dsu.occupy(slot);
        }
    }
    return total;
}

---

Dry-run on the sample

text
pages      = [ 2, 6, 10, 13 ]
threshold  = [ 2, 1, 1, 1 ]
deadlines  = [ 1, 0, 0, 0 ]     // threshold − 1
sorted jobs: (13,0) (10,0) (6,0) (2,1)

 slot 0 free → take 13       total = 13
 slot 0 now busy

 next job (10,0) → no free slot ≤0   (skip)
 next job ( 6,0) → no free slot ≤0   (skip)
 next job ( 2,1) → slot 1 free → take 2   total = 15

15 matches the expected answer.

---

Why it’s optimal

The union-find procedure is the well-known optimal greedy for job sequencing:

We always try to schedule the most valuable remaining printer in the latest still-available slot it can fit; if no such slot exists, the printer can never be used without violating some other printer’s deadline, so skipping it cannot hurt any better solution.

Hence the algorithm yields the maximum total pages that can be printed before the first suspension event.