1235. Maximum Profit in Job Scheduling LeetCode Solution

Last updated: February 22, 2025

In this guide, you will get 1235. Maximum Profit in Job Scheduling LeetCode Solution with the best time and space complexity. The solution to Maximum Profit in Job Scheduling problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Profit in Job Scheduling solution in C++
Maximum Profit in Job Scheduling solution in Java
Maximum Profit in Job Scheduling solution in Python
Additional Resources

1235. Maximum Profit in Job Scheduling LeetCode Solution image

Problem Statement of 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.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job.
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job.
Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

1 <= startTime.length == endTime.length == profit.length <= 5 * 104
1 <= startTime[i] < endTime[i] <= 109
1 <= profit[i] <= 104

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(n)

1235. Maximum Profit in Job Scheduling LeetCode Solution in C++

struct Job {
  int startTime;
  int endTime;
  int profit;
};

class Solution {
 public:
  int jobScheduling(vector<int>& startTime, vector<int>& endTime,
                    vector<int>& profit) {
    const int n = startTime.size();
    vector<int> mem(n + 1);
    vector<Job> jobs;

    for (int i = 0; i < n; ++i)
      jobs.emplace_back(startTime[i], endTime[i], profit[i]);

    ranges::sort(jobs, ranges::less{},
                 [](const Job& job) { return job.startTime; });

    // Will use binary search to find the first available start time.
    for (int i = 0; i < n; ++i)
      startTime[i] = jobs[i].startTime;

    return jobScheduling(jobs, startTime, 0, mem);
  }

 private:
  // Returns the maximum profit to schedule jobs[i..n).
  int jobScheduling(const vector<Job>& jobs, const vector<int>& startTime,
                    int i, vector<int>& mem) {
    if (i == jobs.size())
      return 0;
    if (mem[i] > 0)
      return mem[i];

    const int j = firstGreaterEqual(startTime, i + 1, jobs[i].endTime);
    const int pick = jobs[i].profit + jobScheduling(jobs, startTime, j, mem);
    const int skip = jobScheduling(jobs, startTime, i + 1, mem);
    return mem[i] = max(pick, skip);
  }

  int firstGreaterEqual(const vector<int>& arr, int startFrom, int target) {
    return lower_bound(arr.begin() + startFrom, arr.end(), target) -
           arr.begin();
  }
};
/* code provided by PROGIEZ */

1235. Maximum Profit in Job Scheduling LeetCode Solution in Java

class Solution {
  public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
    final int n = startTime.length;
    int[] mem = new int[n + 1];
    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) -> Integer.compare(a.startTime, b.startTime));

    // Will use binary search to find the first available start time.
    for (int i = 0; i < n; ++i)
      startTime[i] = jobs[i].startTime;

    return jobScheduling(jobs, startTime, 0, mem);
  }

  private record Job(int startTime, int endTime, int profit) {}

  private int jobScheduling(Job[] jobs, int[] startTime, int i, int[] mem) {
    if (i == jobs.length)
      return 0;
    if (mem[i] > 0)
      return mem[i];

    final int j = firstGreaterEqual(startTime, i + 1, jobs[i].endTime);
    final int pick = jobs[i].profit + jobScheduling(jobs, startTime, j, mem);
    final int skip = jobScheduling(jobs, startTime, i + 1, mem);
    return mem[i] = Math.max(pick, skip);
  }

  private int firstGreaterEqual(int[] arr, int startFrom, int target) {
    int l = startFrom;
    int r = arr.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (arr[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}
// code provided by PROGIEZ

1235. Maximum Profit in Job Scheduling LeetCode Solution in Python

class Solution:
  def jobScheduling(
      self,
      startTime: list[int],
      endTime: list[int],
      profit: list[int],
  ) -> int:
    jobs = sorted([(s, e, p) for s, e, p in zip(startTime, endTime, profit)])

    # Will use binary search to find the first available startTime
    for i in range(len(startTime)):
      startTime[i] = jobs[i][0]

    @functools.lru_cache(None)
    def dp(i: int) -> int:
      """Returns the maximum profit to schedule jobs[i..n)."""
      if i == len(startTime):
        return 0
      j = bisect.bisect_left(startTime, jobs[i][1])
      return max(jobs[i][2] + dp(j), dp(i + 1))

    return dp(0)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents