A script that calculate process scheduling in a theoretical infinitely powerful computer.

process.py

import itertools
from decimal import Decimal

class Runtime:

    def __init__(self, proc, start, end):
        self.proc = proc
        self.start = start
        self.end = end

    def __repr__(self):
        return "From %s to %s" % (self.start, self.end)
    
    @property
    def length(self):
        return self.end-self.start

class Process:
    
    def __init__(self, pk, start, end, units):
        self.pk = pk
        self.start = start
        self.end = end
        self.units = units
        self.runtimes = [Runtime(self, start, end)]

    @property
    def rate(self):
        return (self.units / self.runtime) if self.runtime != 0 else Decimal("inf")

    @property
    def runtime(self):
        return sum(runtime.length for runtime in self.runtimes)

    def __repr__(self):
        return "%d units of work between %ds and %ds (%s, %s)" % (self.units, self.start, self.end, self.rate, self.runtime)

class ProcList(list):
    
    def get_conflict(self):
        times = [item for proc in self for item in proc.runtimes]
        ends = sorted(list(set([item.start for item in times]+[item.end for item in times])))
        for i in range(len(ends)-1):
            start = ends[i]
            end = ends[i+1]
            conflicts = [runtime for runtime in times if runtime.start < end and runtime.end > start]
            if len(conflicts)>1:
                return (start, end, conflicts)

    def sanitize(self):
        for proc in self:
            proc.runtimes = [runtime for runtime in proc.runtimes if runtime.length != 0]
            while True:
                for r1 in proc.runtimes:
                    for r2 in proc.runtimes:
                        if r1.end == r2.start:
                            proc.runtimes.remove(r1)
                            proc.runtimes.remove(r2)
                            proc.runtimes.append(Runtime(proc, r1.start, r2.end))
                            continue
                break

    def balance(self):
        runtimes = sorted([item for proc in self for item in proc.runtimes], key = lambda runtime:runtime.start)
        changed = True
        for i in range(100):
            changed = False
            for i in range(len(runtimes)-1):
                first = runtimes[i]
                second = runtimes[i + 1]
                if first.proc.rate > second.proc.rate:
                    while first.proc.rate > second.proc.rate and first.end < first.proc.end and second.length > 0:
                        changed = True
                        first.end += Decimal(".01")
                        second.start += Decimal(".01")
                else:
                    while first.proc.rate < second.proc.rate and second.start > second.proc.start and first.length > 0:
                        changed = True
                        first.end -= Decimal(".01")
                        second.start -= Decimal(".01")

    def resolve(self):
        while True:
            conflict = self.get_conflict()
            if conflict is None:
                break
            runtimes = []
            for runtime in conflict[2]:
                proc = runtime.proc
                if runtime.end > conflict[1]:
                    proc.runtimes.append(Runtime(proc, conflict[1], runtime.end))
                if runtime.start < conflict[0]:
                    proc.runtimes.append(Runtime(proc, runtime.start, conflict[0]))
                proc.runtimes.remove(runtime)
                test = Runtime(proc, conflict[0], conflict[0])
                proc.runtimes.append(test)
                runtimes.append(test)
            for i in range(int(conflict[0]*100), int(conflict[1]*100)):
                runtimes = sorted(runtimes, reverse=True, key=lambda runtime:runtime.proc.rate)
                runtimes[0].end += Decimal(".01")
            runtimes = sorted(runtimes, key=lambda runtime:runtime.proc.pk)
            start = 0
            for runtime in runtimes:
                runtime.start += start
                runtime.end += start
                start += runtime.length
            for proc in self:
                proc.runtimes = [runtime for runtime in proc.runtimes if runtime.length != 0]

if __name__ == '__main__':
    procs = ProcList()

    #Load up the test case
    pk = 1
    while True:
        i = raw_input()
        if not i:
            break
        start, end, units = (Decimal(x) for x in i.split())
        procs.append(Process(pk, start, end, units))
        pk += 1

    procs.resolve()
    procs.sanitize()
    procs.balance()

    print [proc for proc in procs]
    print [proc.runtimes for proc in procs]