Playground – Schedule Problem – Greedy vs NonGreedy Algorithm

main.py

from timeit import default_timer as timer
from random import randrange, choice
from itertools import combinations
from dataclasses import dataclass
from operator import attrgetter

from io import StringIO
from typing import List, Optional, Sequence, Tuple

@dataclass
class Class:
    name: str
    start: int
    end: int

    @classmethod
    def random_instance(cls, name):
        start = randrange(0, 2400, 100) + choice([0, 15, 30, 45])
        end = start + choice([30, 45, 100, 130, 200, 230])
        return Class(name, start, end)

class Timetable:
    def __init__(self, classes: List[Class]) -> None:
        self.timetable_by_start = sorted(classes, key=attrgetter('start'))
        self.timetable_by_end = sorted(classes, key=attrgetter('end'))

    def first_class_by_end(self) -> Class:
        return self.timetable_by_end[0]

    def first_class_starts_after(self, start: int) -> Optional[Class]:
        for class_ in self.timetable_by_start:
            if class_.start >= start:
                return class_

    def __repr__(self) -> str:
        timetable = StringIO()
        for class_ in self.timetable_by_start:
            timetable.write(f'{class_.name:<8}\t{class_.start:0>4}\t{class_.end:>4}\n')
        return timetable.getvalue()

class NonGreedyScheduler:
    def _has_overlap(self, schedule: Sequence[Class]) -> bool:
        for index, element in enumerate(schedule[:-1]):
            if element.end > schedule[index + 1].start:
                return True
        return False

    def perform(self, timetable: Timetable) -> Tuple[Timetable, int]:
        start = timer()
        candidates_schedules = []
        for L in range(0, len(timetable.timetable_by_start) + 1):
            for candidate_schedule in combinations(timetable.timetable_by_start, L):
                if not self._has_overlap(candidate_schedule):
                    candidates_schedules.append(candidate_schedule)
        candidates_schedules.sort(key=lambda schedule: len(schedule), reverse=True)
        elapsed_time = timer() - start
        return Timetable(candidates_schedules[0]), elapsed_time

class GreedyScheduler:
    def perform(self, timetable: Timetable) -> Tuple[Timetable, int]:
        start = timer()
        schedule = []
        class_ = timetable.first_class_by_end()
        while class_:
            schedule.append(class_)
            class_ = timetable.first_class_starts_after(class_.end)
        elapsed_time = timer() - start
        return Timetable(schedule), elapsed_time

courses = [Class.random_instance(f'#{index}') for index in range(25)]
timetable = Timetable(courses)
print(timetable)

scheduler = GreedyScheduler()
schedule, elapsed_time = scheduler.perform(timetable)
print(f'Elapsed Time: {elapsed_time}')
print(schedule)


scheduler = NonGreedyScheduler()
schedule, elapsed_time = scheduler.perform(timetable)
print(f'Elapsed Time: {elapsed_time}')
print(schedule)