Skip to content

1235. Maximum Profit in Job Scheduling 👍

Approach 1: Top-down

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct Job {
  int startTime;
  int endTime;
  int profit;
  Job(int startTime, int endTime, int profit)
      : startTime(startTime), endTime(endTime), profit(profit) {}
};

class Solution {
 public:
  int jobScheduling(vector<int>& startTime, vector<int>& endTime,
                    vector<int>& profit) {
    const int n = startTime.size();
    // dp[i] := max profit to schedule jobs[i:]
    dp.resize(n + 1);
    vector<Job> jobs;

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

    sort(begin(jobs), end(jobs), [](const auto& a, const auto& b) {
      return a.startTime < b.startTime;
    });

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

    return jobScheduling(jobs, startTime, 0);
  }

 private:
  vector<int> dp;

  int jobScheduling(const vector<Job>& jobs, const vector<int>& startTime,
                    int i) {
    if (i == jobs.size())
      return 0;
    if (dp[i] > 0)
      return dp[i];

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

  int firstGreaterEqual(const vector<int>& A, int startFrom, int target) {
    return lower_bound(begin(A) + startFrom, end(A), target) - begin(A);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Job {
  public int startTime;
  public int endTime;
  public int 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) {
    final int n = startTime.length;
    // dp[i] := max profit to schedule jobs[i:]
    dp = 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) -> a.startTime - b.startTime);

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

    return jobScheduling(jobs, startTime, 0);
  }

  private int[] dp;

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

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

  private int firstGreaterEqual(int[] A, int startFrom, int target) {
    int l = startFrom;
    int r = A.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (A[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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]

    # dp(i) := max profit to schedule jobs[i:]
    @lru_cache(None)
    def dp(i: int) -> int:
      if i == len(startTime):
        return 0

      j = bisect_left(startTime, jobs[i][1])
      return max(jobs[i][2] + dp(j), dp(i + 1))

    return dp(0)

Approach 2: Bottom-up

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
struct Job {
  int startTime;
  int endTime;
  int profit;
  Job(int startTime, int endTime, int profit)
      : startTime(startTime), endTime(endTime), profit(profit) {}
};

class Solution {
 public:
  int jobScheduling(vector<int>& startTime, vector<int>& endTime,
                    vector<int>& profit) {
    const int n = startTime.size();
    // dp[i] := max profit to schedule jobs[i:]
    vector<int> dp(n + 1);
    vector<Job> jobs;

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

    sort(begin(jobs), end(jobs), [](const auto& a, const auto& b) {
      return a.startTime < b.startTime;
    });

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

    for (int i = n - 1; i >= 0; --i) {
      const int j = firstGreaterEqual(startTime, i + 1, jobs[i].endTime);
      const int choose = jobs[i].profit + dp[j];
      const int skip = dp[i + 1];
      dp[i] = max(choose, skip);
    }

    return dp[0];
  }

  int firstGreaterEqual(const vector<int>& A, int startFrom, int target) {
    return lower_bound(begin(A) + startFrom, end(A), target) - begin(A);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Job {
  public int startTime;
  public int endTime;
  public int 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) {
    final int n = startTime.length;
    // dp[i] := max profit to schedule jobs[i:]
    int[] dp = 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) -> a.startTime - b.startTime);

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

    for (int i = n - 1; i >= 0; --i) {
      final int j = firstGreaterEqual(startTime, i + 1, jobs[i].endTime);
      final int choose = jobs[i].profit + dp[j];
      final int skip = dp[i + 1];
      dp[i] = Math.max(choose, skip);
    }

    return dp[0];
  }

  private int firstGreaterEqual(int[] A, int startFrom, int target) {
    int l = startFrom;
    int r = A.length;
    while (l < r) {
      final int m = (l + r) / 2;
      if (A[m] >= target)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    # dp[i] := max profit to schedule jobs[i:]
    dp = [0] * (len(startTime) + 1)
    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]

    for i in reversed(range(len(startTime))):
      j = bisect_left(startTime, jobs[i][1])
      dp[i] = max(jobs[i][2] + dp[j], dp[i + 1])

    return dp[0]

Approach 3: Heap

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct Job {
  int startTime;
  int endTime;
  int profit;
  Job(int startTime, int endTime, int profit)
      : startTime(startTime), endTime(endTime), profit(profit) {}
};

class Solution {
 public:
  int jobScheduling(vector<int>& startTime, vector<int>& endTime,
                    vector<int>& profit) {
    vector<Job> jobs;

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

    sort(begin(jobs), end(jobs), [](const auto& a, const auto& b) {
      return a.startTime < b.startTime;
    });

    return getMaxProfit(jobs);
  }

 private:
  int getMaxProfit(const vector<Job>& jobs) {
    int maxProfit = 0;
    auto compare = [](const Job& a, const Job& b) {
      return a.endTime > b.endTime;
    };
    priority_queue<Job, vector<Job>, decltype(compare)> minHeap(compare);

    for (const auto& [s, e, p] : jobs) {
      while (!minHeap.empty() && s >= minHeap.top().endTime)
        maxProfit = max(maxProfit, minHeap.top().profit), minHeap.pop();
      minHeap.emplace(s, e, p + maxProfit);
    }

    while (!minHeap.empty())
      maxProfit = max(maxProfit, minHeap.top().profit), minHeap.pop();

    return maxProfit;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Job {
  public int startTime;
  public int endTime;
  public int 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) {
    final 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.startTime - b.startTime);

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

    return getMaxProfit(jobs);
  }

  private int getMaxProfit(Job[] jobs) {
    int maxProfit = 0;
    Queue<Job> minHeap = new PriorityQueue<>((a, b) -> a.endTime - b.endTime);

    for (Job job : jobs) {
      while (!minHeap.isEmpty() && job.startTime >= minHeap.peek().endTime)
        maxProfit = Math.max(maxProfit, minHeap.poll().profit);
      minHeap.offer(new Job(job.startTime, job.endTime, job.profit + maxProfit));
    }

    while (!minHeap.isEmpty())
      maxProfit = Math.max(maxProfit, minHeap.poll().profit);

    return maxProfit;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    maxProfit = 0
    jobs = sorted([(s, e, p) for s, e, p in zip(startTime, endTime, profit)])
    minHeap = []  # (endTime, profit)

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

    for s, e, p in jobs:
      while minHeap and s >= minHeap[0][0]:
        maxProfit = max(maxProfit, heapq.heappop(minHeap)[1])
      heapq.heappush(minHeap, (e, p + maxProfit))

    return max(maxProfit, max(p for _, p in minHeap))
Back to top