Алгоритми Юли 2017 Processor Scheduling
След доста мислене над тази задача се отказах и реших да погледна видеото от упражнението. Оказа се че колегата Грамов също се затрудни с нея. Разбираемо имайки предвид странно и неясно написаното условие. На 02:16:10 във видеото се вижда условие което judge системата възнаграждава със 100 точки. Това е решението преписано дословно. Реших да го препиша и дебъгна за да видя как работи и какво точно съм пропуснал. Идеята е да вземе най-големия срок и да го използва като лимит за броя на задачите които могат да се изпълнят преди него. Оказа се, обаче, че и то не следва условието на задачата - докато се опитвах да я напиша си създадох няколко теста, освен дадените, с цел да следя поведението на алгоритъма в различни ситуации. Пример:
Tasks: 6
5 - 1
6 - 1
2 - 1
3 - 1
8 - 4
4 - 1
максималния брой задачи, които могат да се изпълнят е 2 - една която има deadline 1 и тази с deadline 4, тъй като по условие всяка задача се изпълнява за една единица време. Тоест изпълнявайки една от задачите всички (други) с deadline 1 не би трябвало да могат да се изпълнят тъй като срока им е минал. Въпреки това алгоритъма взима най-големия deadline - в случая 4 - и добавя задачи в списък докато броят на добавените елементи не стигне до maxDeadline (foreach loop-а на ред 27 от решението).
EDIT: Забравих да постна условието.
Някой може ли да удари едно рамо с решение което всъщност отговаря на условието?
Работи безотказно! Интересен подход. Не би ми хрумнало подобно решение. Cheers!