Skip to content

Instantly share code, notes, and snippets.

Created April 12, 2021 03:06
What would you like to do?
Playground – Schedule Problem – Greedy vs NonGreedy Algorithm
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
class Class:
name: str
start: int
end: int
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:
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.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_:
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)
scheduler = GreedyScheduler()
schedule, elapsed_time = scheduler.perform(timetable)
print(f'Elapsed Time: {elapsed_time}')
scheduler = NonGreedyScheduler()
schedule, elapsed_time = scheduler.perform(timetable)
print(f'Elapsed Time: {elapsed_time}')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment