Untitled

#!/usr/bin/env python3
import sys
 
 
def parse_input(file):
    with open(file) as f:
        n = int(f.readline())
        p, r, d = [], [], []
        for line in f:
            p_i, r_i, d_i = map(int, line.split())
            p.append(p_i)
            r.append(r_i)
            d.append(d_i)
    return n, p, r, d
 
 
class Scheduler:
    def __init__(self, n, p, r, d, ub):
        self.best = []
        self.upper_bound = ub
        self.n = n
        self.p = p
        self.r = r
        self.d = d
 
 
def compute(best, n, r, p):
    if len(best) == 0:
        return [-1]
    c = 0
    schedule = [0 for _ in range(n)]
    for i in best:
        t = max(c, r[i])
        c = t + p[i]
        schedule[i] = t
    return schedule
 
 
def branch_and_bound(scheduled_tasks, not_sch_tasks, len_of_partial_sch, scheduler):
    # missed deadline: (∃ Tj ∈ V: max{c, rj} + pj > dj) ⇒ prune this node
    for i in not_sch_tasks:
        if scheduler.d[i] < max(len_of_partial_sch, scheduler.r[i]) + scheduler.p[i]:
            return False
 
    # bound on the solution
    if not not_sch_tasks:
        if scheduler.upper_bound is None or scheduler.upper_bound > len_of_partial_sch:
            scheduler.best = scheduled_tasks
            scheduler.upper_bound = len_of_partial_sch
        return False
    else:
        lower_bound = max(len_of_partial_sch,
                          min(scheduler.r[i] for i in not_sch_tasks)) \
                      + sum(scheduler.p[i] for i in not_sch_tasks)
        if scheduler.upper_bound is None:
            ub = max(scheduler.d[i] for i in not_sch_tasks)
            if lower_bound > ub:
                return False
        elif lower_bound >= scheduler.upper_bound:
            return False
 
    # decomposition, c ≤ min(Tj∈V) {rj }) ⇒ do not backtrack.
    part_sol = False
    if len_of_partial_sch <= min(scheduler.r[i] for i in not_sch_tasks):
        scheduler.best = scheduler.best + scheduled_tasks
        part_sol = True
 
    for i, task in enumerate(not_sch_tasks):
        new_partial_sch = max(len_of_partial_sch, scheduler.r[task]) + scheduler.p[task]
        new_not_sch_tasks = [t for idx, t in enumerate(not_sch_tasks) if idx != i]
        if branch_and_bound(scheduled_tasks + [task], new_not_sch_tasks, new_partial_sch, scheduler):
            return True
    return part_sol
 
 
# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    n, p, r, d = parse_input(sys.argv[1])
    scheduler = Scheduler(n, p, r, d, None)
 
    scheduled, not_scheduled = [], [i for i in range(n)]
    branch_and_bound(scheduled, not_scheduled, 0, scheduler)
 
    res = compute(scheduler.best, scheduler.n, scheduler.r, scheduler.p)
 
    # print(schd.upper_bound)
 
    for s in res:
        print(s)
 
    with open(sys.argv[2], "w") as f:
        for s in res:
            f.write(str(s) + "\n")