Untitled

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

class Scheduler {
public:
    std::vector<int> best;
    int upper_bound;
    int n;
    std::vector<int> p, r, d;

    Scheduler(int n, const std::vector<int> &p, const std::vector<int> &r, const std::vector<int> &d, int ub)
            : upper_bound(ub), n(n), p(p), r(r), d(d) {}
};

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

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

    // missed deadline: (∃ Tj ∈ V: max{c, rj} + pj > dj) ⇒ prune this node
    for (int i: not_sch_tasks) {
        if (scheduler.d[i] < std::max(len_of_partial_sch, scheduler.r[i]) + scheduler.p[i]) {
            return false;
        }
    }

    // bound on the solution
    if (not_sch_tasks.empty()) {
        if (scheduler.upper_bound == -1 || scheduler.upper_bound > len_of_partial_sch) {
            scheduler.best = scheduled_tasks;
            scheduler.upper_bound = len_of_partial_sch;
        }
        return false;
    } else {
        int r_min = INT_MAX;
        for (int task: not_sch_tasks) {
            r_min = std::min(r_min, scheduler.r[task]);
        }

        int p_sum = std::accumulate(not_sch_tasks.begin(), not_sch_tasks.end(), 0,
                                    [&scheduler](int acc, int i) { return acc + scheduler.p[i]; });
        int lower_bound = std::max(len_of_partial_sch, std::max(len_of_partial_sch, r_min)) + p_sum;

        if (scheduler.upper_bound == -1) {
            int ub = -1;
            for (int task: not_sch_tasks) {
                ub = std::max(ub, scheduler.d[task]);
            }
            if (lower_bound > ub) {
                return false;
            }
        } else if (lower_bound >= scheduler.upper_bound) {
            return false;
        }
    }

    // decomposition, c ≤ min(Tj∈V) {rj }) ⇒ do not backtrack.
    bool part_sol = false;
    int max_r = -1;
    for (int i: not_sch_tasks) {
        max_r = std::max(max_r, scheduler.r[i]);
    }
    if (len_of_partial_sch <= max_r) {
        scheduler.best.insert(scheduler.best.end(), scheduled_tasks.begin(), scheduled_tasks.end());
        part_sol = true;
    }

    for (int i: not_sch_tasks) {
        std::vector<int> new_partial_sch(scheduled_tasks);
        new_partial_sch.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(new_partial_sch, new_not_sch_tasks,
                             std::max(len_of_partial_sch, scheduler.r[i]) + scheduler.p[i], scheduler)) {
            return true;
        }
    }
    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;
    std::vector<int> p, r, d;
    parse_input(argv[1], n, p, r, d);
    Scheduler scheduler(n, p, r, d, -1);

    std::vector<int> scheduled, not_scheduled;
    for (int i = 0; i < n; ++i) {
        not_scheduled.push_back(i);
    }

    branch_and_bound(scheduled, not_scheduled, 0, scheduler);

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

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

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

    return 0;
}