| 10 | |
| 11 | |
| 12 | class Scheduling: |
| 13 | def __init__(self, jobs: List[int]) -> None: |
| 14 | """ |
| 15 | Assign jobs as instance of class Scheduling |
| 16 | """ |
| 17 | self.jobs = jobs |
| 18 | |
| 19 | def schedule(self, total_jobs: int, deadline: List[int]) -> List[int]: |
| 20 | """ |
| 21 | Parameteres : total_jobs and list of deadline of jobs |
| 22 | Returns : List of jobs_id which are profitable and can be done before |
| 23 | deadline |
| 24 | >>> a = Scheduling([(0, 13, 10),(1, 2, 20),(2, 33, 30),(3, 16, 40)]) |
| 25 | >>> a.schedule( 3, [3, 4, 5]) |
| 26 | [(1, 2, 20), (2, 33, 30)] |
| 27 | >>> a = Scheduling([(0, 13, 10),(1, 2, 20),(2, 33, 30),(3, 16, 40)]) |
| 28 | >>> a.schedule( 4, [13, 2, 33, 16]) |
| 29 | [(1, 2, 20), (2, 33, 30), (3, 16, 40)] |
| 30 | """ |
| 31 | self.j = [self.jobs[1]] |
| 32 | self.x = 2 |
| 33 | while self.x < total_jobs: |
| 34 | self.k = self.j.copy() |
| 35 | self.k.append(self.jobs[self.x]) |
| 36 | self.x += 1 |
| 37 | if self.feasible(self.k, deadline): |
| 38 | self.j = self.k.copy() |
| 39 | |
| 40 | return self.j |
| 41 | |
| 42 | def feasible(self, profit_jobs: List[int], deadline: List[int]) -> bool: |
| 43 | """ |
| 44 | Parameters : list of current profitable jobs within deadline |
| 45 | list of deadline of jobs |
| 46 | Returns : true if k[-1] job is profitable to us else false |
| 47 | >>> a = Scheduling([(0, 13, 10),(1, 2, 20),(2, 33, 30),(3, 16, 40)]) |
| 48 | >>> a.feasible( [0], [2, 13, 16, 33] ) |
| 49 | True |
| 50 | >>> a = Scheduling([(0, 13, 10),(1, 2, 20),(2, 33, 30),(3, 16, 40)]) |
| 51 | >>> a.feasible([0], [2, 13, 16, 33] ) |
| 52 | True |
| 53 | """ |
| 54 | |
| 55 | self.tmp = profit_jobs |
| 56 | self.is_feasible = True |
| 57 | |
| 58 | i = 0 |
| 59 | j = 1 |
| 60 | k = 0 |
| 61 | |
| 62 | while i < len(self.tmp): |
| 63 | while j < len(self.tmp): |
| 64 | self.index1 = self.jobs.index(self.tmp[i]) |
| 65 | self.index2 = self.jobs.index(self.tmp[j]) |
| 66 | j += 1 |
| 67 | if deadline[self.index1] > deadline[self.index2]: |
| 68 | (self.tmp[i], self.tmp[j]) = ( |
| 69 | self.tmp[j], |