Job Sequencing Problem Find and Union
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(); } } |
JobSequencingProblemFindAndUnion.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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 |
package com.omt.learn.geekforgeek.greedy; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.List; import java.util.Map; import java.util.TreeMap; import com.omt.learn.algo.util.job.JobSequence; public class JobSequencingProblemFindAndUnion { public static void main(String[] args) { printJobSequence(getInputOne()); printJobSequence(getInputTwo()); printJobSequence(getInputThree()); } public static void printJobSequence(List<JobSequence> jobSequences) { // Sorting to get Max Deadline Collections.sort(jobSequences, new Comparator<JobSequence>() { @Override public int compare(JobSequence o1, JobSequence o2) { return -(o1.getDeadline() - o2.getDeadline()); } @Override public boolean equals(Object obj) { return super.equals(obj); } }); // Get Max deadline int maxDeadLine = jobSequences.get(0).getDeadline(); // Sort again with profit Collections.sort(jobSequences, Collections.reverseOrder()); int sizeOfSubset = maxDeadLine + 1; // Create subset with size of maxDeadLine and assign default value. int[] subset = new int[sizeOfSubset]; for (int count = 0; count < sizeOfSubset; count++) { subset[count] = count; } Map<Integer, JobSequence> positionJobSequenceMap = new TreeMap<>(); for (JobSequence jobSequence : jobSequences) { int availablePosition = find(jobSequence.getDeadline(), subset); if (availablePosition > 0) { int nextAvailablePosition = find(availablePosition - 1, subset); positionJobSequenceMap.put(availablePosition, jobSequence); union(availablePosition, nextAvailablePosition, subset); } } StringBuilder result = new StringBuilder(); for (Integer position : positionJobSequenceMap.keySet()) { result.append(positionJobSequenceMap.get(position).getJobId() + ","); } System.out.println(result.toString()); } public static int find(int position, int[] subset) { if (subset[position] == position) { return position; } return find(subset[position], subset); } public static void union(int position, int nextAvailable, int[] subset) { subset[position] = nextAvailable; } 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, |
