package org.wesome.dsalgo;
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;
@Data
@AllArgsConstructor
@NoArgsConstructor
class Job {
int taskId, deadline, profit;
}
public class JobSequence {
public static int jobSchedule(List<Job> jobs, int maxDeadLine) {
int totalProfit = 0;
int[] timeSlot = new int[maxDeadLine];
/* default value of int is 1, but 1 can also be a valid time slot, hence fill the array with -1 */
Arrays.fill(timeSlot, -1);
/* sort the jobs accounting to the highest Profit */
Collections.sort(jobs, (jobA, jobB) -> jobB.profit - jobA.profit);
// consider each job in decreasing order of their profits
for (Job job : jobs) {
/* loop till current job fits into deadline array */
for (int deadLine = job.deadline - 1; deadLine >= 0; deadLine--) {
/* loop till the maximum deadline available and the time slot for current deadline should be empty */
if (deadLine < maxDeadLine && timeSlot[deadLine] == -1) {
timeSlot[deadLine] = job.taskId;
totalProfit += job.profit;
/* valid position for this task is found, no need to iterate further, break the loop */
break;
}
}
}
System.out.println("The jobs with maximum profit are " + Arrays.stream(timeSlot).filter(slot -> slot != -1).boxed().collect(Collectors.toList()) + " and the total totalProfit earned by these jobs is " + totalProfit);
return totalProfit;
}
}
package org.wesome.dsalgo;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import java.util.Arrays;
import java.util.List;
import static org.wesome.dsalgo.JobSequence.jobSchedule;
public class JobSequenceTest {
@Test
void jobScheduleTest() {
List<Job> jobs = Arrays.asList(new Job(1, 9, 15),
new Job(2, 2, 2),
new Job(3, 5, 18),
new Job(4, 7, 1),
new Job(5, 4, 25),
new Job(6, 2, 20),
new Job(7, 5, 8),
new Job(8, 7, 10),
new Job(9, 4, 12),
new Job(10, 3, 5));
int maxDeadLine = 15;
Assertions.assertEquals(109, jobSchedule(jobs, maxDeadLine));
}
}
plugins {
id 'java'
id "io.freefair.lombok" version "6.2.0"
}
group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8
configurations {
compileOnly {
extendsFrom annotationProcessor
}
}
repositories {
mavenCentral()
}
dependencies {
testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}
test {
useJUnitPlatform()
}