Job Sequencing Problem
Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.
JobSequence.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
package com.omt.learn.algo.util.job; public class JobSequence implements Comparable<JobSequence> { private String jobId; private int deadline = -1; private int profit = -1; public JobSequence(String jobId, int deadline, int profit) { this.jobId = jobId; this.deadline = deadline; this.profit = profit; } public String getJobId() { return jobId; } public int getDeadline() { return deadline; } public int getProfit() { return profit; } @Override public int compareTo(JobSequence o) { return this.profit - o.getProfit(); } } |
JobSequencingProblem.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
package com.omt.learn.geekforgeek.greedy; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Map; import java.util.TreeMap; import com.omt.learn.algo.util.job.JobSequence; public class JobSequencingProblem { public static void main(String[] args) { printJobSequence(getInputOne()); printJobSequence(getInputTwo()); printJobSequence(getInputThree()); } public static void printJobSequence(List<JobSequence> jobSequences) { Collections.sort(jobSequences, Collections.reverseOrder()); StringBuilder result = new StringBuilder(); Map<Integer, JobSequence> positions = new TreeMap<>(); for (JobSequence jobSequence : jobSequences) { int position = jobSequence.getDeadline(); while (position > 0) { position--; if (!positions.containsKey(position)) { positions.put(position, jobSequence); break; } } } for (Integer position : positions.keySet()) { result.append(positions.get(position).getJobId() + ","); } System.out.println(result.toString()); } public static List<JobSequence> getInputOne() { List<JobSequence> jobSequences = new ArrayList<>(); jobSequences.add(new JobSequence("a", 4, 20)); jobSequences.add(new JobSequence("b", 1, 10)); jobSequences.add(new JobSequence("c", 1, 40)); jobSequences.add(new JobSequence("d", 1, 30)); return jobSequences; } public static List<JobSequence> getInputTwo() { List<JobSequence> jobSequences = new ArrayList<>(); jobSequences.add(new JobSequence("g", 7, 30)); jobSequences.add(new JobSequence("a", 4, 100)); jobSequences.add(new JobSequence("e", 3, 70)); jobSequences.add(new JobSequence("f", 3, 50)); jobSequences.add(new JobSequence("c", 3, 80)); jobSequences.add(new JobSequence("d", 3, 75)); jobSequences.add(new JobSequence("b", 4, 90)); return jobSequences; } public static List<JobSequence> getInputThree() { List<JobSequence> jobSequences = new ArrayList<>(); jobSequences.add(new JobSequence("a", 2, 100)); jobSequences.add(new JobSequence("e", 3, 15)); jobSequences.add(new JobSequence("c", 2, 27)); jobSequences.add(new JobSequence("d", 1, 25)); jobSequences.add(new JobSequence("b", 1, 19)); return jobSequences; } } |
Output:
|
1 2 3 |
c,a, d,c,b,a,g, c,a,e, |
