sinasina444 / job-scheduler Goto Github PK

Job Scheduler

Given a list of jobs you accept a subset of the jobs, rejecting all others, so that the accepted jobs do not overlap in time.

More formally, there will be n jobs labeled 1...n with each job, j, specifying a start time Sj and a finish time Tj. Naturally we have Sj < Tj for all j. Two jobs j and j1 are compatible if the requested intervals do not overlap; that is, either job j is for an earlier time interval than job j1 (Tj <= Sj1), or job j is for a later time than job j1 (Tj1 <= Sj). More generally, that a subset A of jobs is compatible if all pairs of jobs j,j1 within A, j != j1 are compatible. The goal is to select a compatible subset of jobs of maximum possible size. To illustrate, for the following jobs the single compatible set of size 4 is the largest compatible set.

Task 1: Select the largest subset from the given jobs such that no jobs overlap in time.

• Greedy approach
• First sort the collection of given jobs by their finish time - O(nlogn)
• Select the first job, then iteratively search through the sorted collection and select the job which doesn't overlap with previously selected job. - O(n)

Final Runtime: O(nlogn)

Task 2: Now each input job has a cost associated with it. Select the maximum total-cost subset of non-overlapping jobs. Now we do not maximize for number of jobs, we want maximum cost subset

• Greedy approach doesn't work.
• Dynamically memoize cost associated with each job such that it doesn't include the cost of overlapping jobs preceding it.
• Backtrack to get the subset.
• First sort the collection of given jobs by their finish time - O(nlogn)
• Find the latest compatible job for each input job - O(n^2)
• Build memoized array of costs - O(n)
• Backtrack recursively to get the subset - O(n)

Final Runtime: O(n^2)