Editorial for Cramming Assignments

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: oree

In this problem, we have a bunch of different assignments that we start working on at different times, and after finishing an assignment, we will print it out and resume any interrupted assignments in order. To maintain this state (time remaining for assignments, and their index to print), we can use a stack. Then, we can maintain the current time as an integer, and loop over all the interrupts. For each interrupt, we can calculate the time spent working as the difference between interrupt time and previous (current) time. Then, in a loop, we can remove time from all the assignments we have, popping if we finish any assignments and proceeding until we have spent all the time worked. Then, we can push the new assignment. Finally, after all interrupts, we just want to finish assignments in order from the stack.

This solution has $O(n)$ ~O(n)~ time complexity, since the loop processes each interrupt. While a single loop iteration may cause lots of assignments to be processed and popped from the stack, each assignment is only popped once over the lifespan of the program. Since the stack could grow if all interrupts are consective without time to finish assignments, the program has $O(n)$ ~O(n)~ space complexity.

C++ solution:

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

int main() {
    int n;
    cin >> n;

    vector<int> lengths(n);
    for (auto& x : lengths)
        cin >> x;

    vector<int> interruptions(n - 1);
    for (auto& x : interruptions)
        cin >> x;

    stack<pair<int, int>> tasks;
    int curtime = 0;

    // We are storing the assignment number (for printing) as well as the remaining time
    tasks.push({ 1, lengths[0] });

    for (int i = 0; i < n - 1; i++) {
        int inttime = interruptions[i];
        // inttime - curtime is the time we have spent working since last interrupt
        int workdone = inttime - curtime;
        while (!tasks.empty() && workdone > 0) {
            auto [idx, remaining] = tasks.top();
            tasks.pop();

            if (workdone >= remaining) {
                // Assignment finished
                cout << "Completed assignment " << idx << " at time " << curtime + remaining << endl;
                workdone -= remaining;
                curtime += remaining;
            } else {
                // Not finished, add to stack with reduced time
                tasks.push({ idx, remaining - workdone });
                break;
            }
        }

        curtime = inttime;
        // We need +2 as its 1-indexed, and also there is no interrupt for a1
        tasks.push({ i + 2, lengths[i + 1] });
    }

    // Complete all unfinished tasks from top to bottom of the stack
    while (!tasks.empty()) {
        auto [idx, remaining] = tasks.top();
        tasks.pop();

        curtime += remaining;
        cout << "Completed assignment " << idx << " at time " << curtime << endl;
    }
}

Python solution:

n = int(input())
lengths = list(map(int, input().split()))
interruptions = list(map(int, input().split()))

stack = [(1, lengths[0])]
curtime = 0

for i in range(n - 1):
    inttime = interruptions[i]
    workdone = inttime - curtime
    # If we are currently doing something, process
    while stack and workdone > 0:
        idx, remaining = stack.pop()

        # If its finished, print it, otherwise add it back with reduced time
        if workdone >= remaining:
            print(f"Completed assignment {idx} at time {curtime + remaining}")
            workdone -= remaining
            curtime += remaining
        else:
            stack.append((idx, remaining - workdone))
            break

    curtime = inttime
    # i+2 as its 1-indexed, and also because we start one forward as a1 is instantly started
    stack.append((i + 2, lengths[i + 1]))

# Process all remaining ones in order
while stack:
    idx, remaining = stack.pop()
    curtime += remaining
    print(f"Completed assignment {idx} at time {curtime}")

Comments

There are no comments at the moment.