1235. Maximum Profit in Job Scheduling

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X

//java code using dynamic programing and back tracking

import java.util.*;
public class leetcodeDaily {
    //static int dir[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static int n;
    static int memo[]=new int[50001];

    //find the first job jiska start time>=current job ka end time
    private static int getNextInd(int[][] arr, int l, int curEndTime) {
        //here we use memoization of dp to store profit as we repetatively call
        int r = n - 1;
        int result = n+1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (arr[mid][0] >= curEndTime) {//we can take the task
                result = mid;
                r = mid - 1;//duplicates can also present so we check
            } else {
                l = mid + 1;
            }

        }
        return result;
    }

    private static int maxProfit(int[][] arr, int index) {
        //base case
        if (index >= n)
            return 0;
        if(memo[index]!=-1)
            return memo[index];
        //if we take current job then only we take another job which start point is greater or equal to end of curr
        //by using binary search we get next job as sorted array is present
        int nextjob = getNextInd(arr, index + 1, arr[index][1]);//take array , curent index +1 and curr end time

        //if we take cur job
        int profit_taken = arr[index][2] + maxProfit(arr, nextjob);//recursive call
        //not taken
        int profit_notTaken = maxProfit(arr, index + 1);

        return memo[index]=Math.max(profit_taken, profit_notTaken);
    }

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

        Arrays.fill(memo,-1);
        //sort the job according to start time . for that we create a array which contains all three value coresponding to
        // each other
        int[][] arr = new int[n][3];
        for (int i = 0; i < n; i++) {
            arr[i][0] = startTime[i];
            arr[i][1] = endTime[i];
            arr[i][2] = profit[i];
        }
        //comparator sort
        Arrays.sort(arr, (x, y) -> x[0] - y[0] != 0 ? x[0] - y[0] : x[1] - y[1]);

        return maxProfit(arr, 0); //this take array and starting index as 0
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int startTime[] = {1, 2, 3, 3}, endTime[] = {3, 4, 5, 6}, profit[] = {50, 10, 40, 70};
        System.out.println(jobScheduling(startTime, endTime, profit));
    }

}