LeetCode 1235: Maximum Profit in Job Scheduling Solution

Master LeetCode problem 1235 (Maximum Profit in Job Scheduling), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1235. Maximum Profit in Job Scheduling

Hard

Array Binary Search Dynamic Programming Sorting

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming with a variation of the weighted interval scheduling algorithm. We first sort the jobs based on their end times. Then we define a dp array to store the maximum profit we can obtain up to a certain job. For each job, we iterate over all previous jobs to find the latest job that doesn't overlap with the current job. We update the dp array with the maximum profit we can achieve by either selecting the current job or not selecting it.

Time Complexity

The time complexity of this approach is O(n log n) for sorting the jobs by end times, and O(n) for iterating through each job, resulting in a total time complexity of O(n log n).

Space Complexity

The space complexity is O(n) to store the dp array.

Solution Code

class Job {
    int start;
    int end;
    int profit;
    
    public Job(int start, int end, int profit) {
        this.start = start;
        this.end = end;
        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, (a, b) -> a.end - b.end);
        
        int[] dp = new int[n];
        dp[0] = jobs[0].profit;
        
        for (int i = 1; i < n; i++) {
            int includeProfit = jobs[i].profit;
            int idx = binarySearch(jobs, i);
            if (idx != -1) {
                includeProfit += dp[idx];
            }
            dp[i] = Math.max(includeProfit, dp[i - 1]);
        }
        
        return dp[n - 1];
    }
    
    private int binarySearch(Job[] jobs, int index) {
        int low = 0, high = index - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (jobs[mid].end <= jobs[index].start) {
                if (jobs[mid + 1].end <= jobs[index].start) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            } else {
                high = mid - 1;
            }
        }
        
        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1235 (Maximum Profit in Job Scheduling)?

This page provides optimized solutions for LeetCode problem 1235 (Maximum Profit in Job Scheduling) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1235 (Maximum Profit in Job Scheduling)?

The time complexity for LeetCode 1235 (Maximum Profit in Job Scheduling) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1235 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1235 in Java, C++, or Python.

Back to LeetCode Solutions