USACO 2024 December Contest Gold Division - Job Completion

Problem link: here

Video link: here

Solution Author: Stefan Dascalescu

Problem Solution

This problem can be solved greedily as we sort the events in the increasing order of the deadline, and then keep using a priority queue the list of events we care about.

As a note for the readers, this problem was also given in a very similar way at the Romanian olympiad, as you can see here.

Source code

The source code in C++ can be seen below.

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

#define int long long

using namespace std;

using ll = long long;

struct jobs {
    int l, d, idx;
    bool operator < (const jobs& e) const {
        return this->d < e.d;
    }
};

void solve() {
    int n; 
    cin >> n;
    std::vector <jobs> v(n), tmp(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i].d >> v[i].l;
        v[i].d += v[i].l;
        v[i].idx = i;
        tmp[i] = v[i];
    }

    sort(v.begin(), v.end());
    multiset <pair <int, int>> s;
    vector <int> sch;
    for (int i = n - 1; i >= 0; --i) {
        int t = v[i].d;
        if (i > 0) {
            t -= v[i-1].d;
        }
        s.insert({v[i].l, v[i].idx});

        while (t and !s.empty()) {
            auto it = s.begin();
            if (it-> first <= t) {
                t -= it-> first;
                sch.emplace_back(it-> second);
            } else {
                s.insert({it-> first - t, it-> second});
                t = 0;
            }
            s.erase(it);
        }
    }

    cout << sch.size() << "\n";
}
signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }
    return 0;
}