Untitled

public class JobScheduler {
    public int minDifficulty(int[] jobDifficulty, int d) {
        int n = jobDifficulty.length;
        // If there are fewer jobs than days, it is impossible to schedule
        if (n < d) return -1;

        return dfs(jobDifficulty, d, 0, n);
    }

    private int dfs(int[] jobDifficulty, int d, int index, int n) {
        // Base case: if we are on the last day, take the maximum difficulty from the remaining jobs
        if (d == 1) {
            int maxDiff = 0;
            for (int i = index; i < n; i++) {
                maxDiff = Math.max(maxDiff, jobDifficulty[i]);
            }
            return maxDiff;
        }

        int maxDiff = 0; // Tracks the maximum difficulty of the current day
        int minDifficulty = Integer.MAX_VALUE; // Tracks the minimum difficulty across all possible splits

        // Explore splitting points
        for (int i = index; i <= n - d; i++) {
            maxDiff = Math.max(maxDiff, jobDifficulty[i]);
            // Recur for the remaining jobs and days
            minDifficulty = Math.min(minDifficulty, maxDiff + dfs(jobDifficulty, d - 1, i + 1, n));
        }

        return minDifficulty;
    }

    public static void main(String[] args) {
        JobScheduler scheduler = new JobScheduler();
        
        int[] jobDifficulty1 = {6, 5, 4, 3, 2, 1};
        int d1 = 2;
        System.out.println(scheduler.minDifficulty(jobDifficulty1, d1)); // Output: 7

        int[] jobDifficulty2 = {9, 9, 9};
        int d2 = 4;
        System.out.println(scheduler.minDifficulty(jobDifficulty2, d2)); // Output: -1

        int[] jobDifficulty3 = {1, 1, 1};
        int d3 = 3;
        System.out.println(scheduler.minDifficulty(jobDifficulty3, d3)); // Output: 3
    }
}