Efficiency is key when it comes to managing multiple jobs with varying start times, end times, and profits. In such scenarios, making the right choices can lead to a significant increase in overall profit. This is where dynamic programming comes to the rescue. In this blog, we’ll explore a Java solution that optimizes job scheduling to maximize profits.

Understanding the Problem

We have a set of jobs, each represented by its start time, end time, and profit. The challenge is to find the maximum profit we can obtain without scheduling overlapping jobs. If two jobs overlap, we can’t perform both simultaneously.

The Java Solution

To tackle this problem efficiently, we create a Job class to represent each job’s attributes—start time, end time, and profit. Additionally, we implement a Solution class with the jobScheduling method to find the maximum profit.

Creating Job Objects

First, we create an array of Job objects, where each object represents a job with its attributes. We populate this array with the data from the input arrays startTime, endTime, and profit.

int n = startTime.length;
Job[] jobs = new Job[n];
for (int i = 0; i < n; i++) {
    jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
}

Sorting by End Times

To maximize profits and minimize overlaps, we sort the jobs array based on the end times of the jobs. This step is crucial for dynamic programming.

Arrays.sort(jobs, Comparator.comparingInt(j -> j.endTime));

Dynamic Programming

We utilize dynamic programming to find the maximum profit while avoiding overlaps. We initialize an array dp to store the maximum profit for each job up to the current position. We start by setting dp[0] to the profit of the first job.

int[] dp = new int[n];
dp[0] = jobs[0].profit;

Next, we iterate through the jobs, calculating the current profit and checking for non-overlapping jobs that can contribute to the profit.

for (int i = 1; i < n; i++) {
    int currentProfit = jobs[i].profit;
    int prevNonOverlappingJob = findPrevNonOverlappingJob(jobs, i);

    if (prevNonOverlappingJob != -1) {
        currentProfit += dp[prevNonOverlappingJob];
    }

    dp[i] = Math.max(currentProfit, dp[i - 1]);
}

The findPrevNonOverlappingJob function helps identify the last non-overlapping job with the current job.

Full Solution

class Job {
    int startTime, endTime, profit;

    public Job(int startTime, int endTime, int profit) {
        this.startTime = startTime;
        this.endTime = endTime;
        this.profit = profit;
    }
}

class Solution {

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
       int n = startTime.length;
        Job[] jobs = new Job[n];

        for (int i = 0; i < n; i++) {
            jobs[i] = new Job(startTime[i], endTime[i], profit[i]);
        }

        Arrays.sort(jobs, Comparator.comparingInt(j -> j.endTime));

        int[] dp = new int[n];
        dp[0] = jobs[0].profit;

        for (int i = 1; i < n; i++) {
            int currentProfit = jobs[i].profit;
            int prevNonOverlappingJob = findPrevNonOverlappingJob(jobs, i);

            if (prevNonOverlappingJob != -1) {
                currentProfit += dp[prevNonOverlappingJob];
            }

            dp[i] = Math.max(currentProfit, dp[i - 1]);
        }

        return dp[n - 1]; 
    }

     private int findPrevNonOverlappingJob(Job[] jobs, int currentJobIndex) {
        for (int i = currentJobIndex - 1; i >= 0; i--) {
            if (jobs[i].endTime <= jobs[currentJobIndex].startTime) {
                return i;
            }
        }
        return -1;
    }
    
}