Untitled

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>

struct Unit {
    int p, r, d;
};

struct Scheduler {
public:
    std::vector<int> best;
    int upper_bound;
    int n;
    std::vector<Unit> units;
};

void parse_input(const std::string &file, int &n, std::vector<Unit> &units, int& upperbound) {
    std::ifstream input(file);
    input >> n;
    units.resize(n);
    int p, r, d;
    int max_d = 0;
    for (int i = 0; i < n; ++i) {
        input >> p >> r >> d;
        units[i] = {p, r, d};
        max_d = std::max(d, max_d);
    }
    upperbound = max_d + 1;
    input.close();
}

std::vector<int> compute(const std::vector<int> &best, int n, std::vector<Unit> units) {
    if (best.empty()) {
        return {-1};
    }
    int c = 0;
    std::vector<int> schedule(n, 0);
    for (int i: best) {
        int t = std::max(c, units[i].r);
        c = t + units[i].p;
        schedule[i] = t;
    }
    return schedule;
}

bool branch_and_bound(std::vector<int> &scheduled_tasks, const std::vector<int> &not_sch_tasks, int len_of_partial_sch,
                      Scheduler &scheduler) {
    int p_sum = 0;
    // missed deadline: (∃ Tj ∈ V: max{c, rj} + pj > dj) ⇒ prune this node
    for (int i: not_sch_tasks) {
        if (scheduler.units[i].d < std::max(len_of_partial_sch, scheduler.units[i].r) + scheduler.units[i].p) {
            return false;
        }
        p_sum += scheduler.units[i].p;
    }

    // bound on the solution
    if (scheduled_tasks.size() == scheduler.n) {
        if (scheduler.upper_bound >= len_of_partial_sch) {
            scheduler.best = scheduled_tasks;
            scheduler.upper_bound = len_of_partial_sch;
        }
        return false;
    }

    int r_min = 1000000000;
    for (int task: not_sch_tasks) {
        r_min = std::min(r_min, scheduler.units[task].r);
    }
    int lower_bound = std::max(len_of_partial_sch, r_min) + p_sum;

    if (lower_bound >= scheduler.upper_bound) {
        return false;
    }

    // decomposition, c ≤ min(Tj∈V) {rj }) ⇒ do not backtrack.
    bool part_sol = false;
    if (len_of_partial_sch <= r_min) {
        part_sol = true;
    }

    for (int i: not_sch_tasks) {
        scheduled_tasks.push_back(i);
        std::vector<int> new_not_sch_tasks;
        for (int task: not_sch_tasks) {
            if (task != i) {
                new_not_sch_tasks.push_back(task);
            }
        }
        if (branch_and_bound(scheduled_tasks, new_not_sch_tasks,
                             std::max(len_of_partial_sch, scheduler.units[i].r) + scheduler.units[i].p, scheduler)) {
            return true;
        }

        scheduled_tasks.pop_back();
    }
    return part_sol;
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        std::cerr << "Usage: " << argv[0] << " input_file output_file\n";
        return 1;
    }

    int n, upperbound;
    std::vector<int> best;
    std::vector<Unit> units;
    parse_input(argv[1], n, units, upperbound);
    Scheduler scheduler = {best, upperbound, n, units};

    std::vector<int> scheduled, not_scheduled(n);
    std::iota(not_scheduled.begin(), not_scheduled.end(), 0);
    std::sort(not_scheduled.begin(), not_scheduled.end(), [&units](const int& a, const int& b) {
        return units[a].d - units[a].p < units[b].d - units[b].p;
    });

    branch_and_bound(scheduled, not_scheduled, 0, scheduler);

    std::vector<int> res = compute(scheduler.best, n, scheduler.units);

//    for (int s: res) {
//        std::cout << s << std::endl;
//    }

    std::ofstream output(argv[2]);
    for (int s: res) {
        output << s << std::endl;
    }

    return 0;
}