Sort + exchange argument (Greedy Sub-pattern)

// The comparator IS the algorithm. Prove it with a swap: if a should come before b,
// swapping them in any answer must not make it better.

// Fractional knapsack: best value per weight first; compare ratios without division.
double fractional(vector<int> val, vector<int> wt, long long cap) {
    int n = val.size();
    vector<int> idx(n);
    iota(idx.begin(), idx.end(), 0);
    sort(idx.begin(), idx.end(), [&](int a, int b) {
        return 1LL * val[a] * wt[b] > 1LL * val[b] * wt[a];  // val[a]/wt[a] > val[b]/wt[b]
    });
    double total = 0;
    for (int i : idx) {
        if (cap == 0) break;
        long long take = min<long long>(cap, wt[i]);
        total += (double)val[i] * take / wt[i];
        cap -= take;
    }
    return total;
}

// Deadlines, one time unit each: by deadline, keep the best profits in a min-heap.
long long maxProfitJobs(vector<pair<int,int>> jobs) {         // {deadline, profit}
    sort(jobs.begin(), jobs.end());
    priority_queue<int, vector<int>, greater<int>> kept;
    for (auto& [d, p] : jobs) {
        kept.push(p);
        if ((int)kept.size() > d) kept.pop();                // too many jobs by time d: drop the cheapest
    }
    long long sum = 0;
    while (!kept.empty()) { sum += kept.top(); kept.pop(); }
    return sum;
}