Python Forum
Job Scheduling to be solved with Greedy algorithm
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Job Scheduling to be solved with Greedy algorithm
#1
I am learning Greedy algorithm, i now want to solve Job Scheduling with this algorithm, say i have a list
list=[(1, 3.0, 6.0), (2, 6.0, 10.0), (3, 1.0, 4.0), (4, 5.0, 7.0), (5, 0.0, 3.0)] 
A picure can illustrate this list 1st number is the job ID(int), the 2nd is the job start time(float), and the 3rd is the finish time(float). Now i want to find the shortest interval of those jobs i.e. jobs are considered in order of shortest to longest interval length, each job is included if and only if it doesn't conflict with previously chosen jobs. Every tuple in the list is actually an object of Class Job Class jobs is written as follows
class Job:

def __init__(self, id, start_time, finish_time):
    self._id = id
    self._start_time = start_time
    self._finish_time = finish_time

def get_id(self):
    return self._id

def get_start_time(self):
    return self._start_time

def get_finish_time(self):
    return self._finish_time

def __repr__(self):
    return "(" + str(self._id) + ", " + str(self._start_time) \
            + ", " + str(self._finish_time) + ")"
So again the question is how to solve Job scheduling(shortest interval) with greedy algorithm and the jobs selected should be compatible( not overlapping with each other) and Return all those non-overlapping jobs with shortest interval Any help is appreciated, thx in advance Smile Smile Smile

For my example list the output should be

[[(5, 0.0, 3.0),(4, 5.0, 7.0)],[(3, 1.0, 4.0),(4, 5.0, 7.0)]]
Reason is that both sub-list have job intervals of 5, and jobs in these two sub-list do not overlap.
Reply
#2
Thx anyway, i myself has figured out the solution
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Non-greedy regex WJSwan 1 880 Mar-07-2023, 09:15 PM
Last Post: Larz60+
  Greedy algorithms on logical problems Opensourcehacker 0 1,507 Nov-22-2020, 05:12 PM
Last Post: Opensourcehacker

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020