Maximum Profit in Job Scheduling LeetCode solution in C++

1
struct Task {
2
  int start, end, profit;
3
  Task(int s, int e, int p) : start(s), end(e), profit(p) {};
4
};
5

6
class Solution {
7
 public:
8
  int jobScheduling(vector<int> &startTime, vector<int> &endTime, vector<int> &profit) {
9
    int n = startTime.size();
10
    // sort by ascending end time
11
    vector<Task> tasks;
12
    for (int i = 0; i < n; i++) tasks.push_back(Task(startTime[i], endTime[i], profit[i]));
13
    auto cmp = [](const Task &t1, const Task &t2) { return t1.end < t2.end; };
14
    sort(tasks.begin(), tasks.end(), cmp);
15

16
    vector<int> dp(n, 0);
17
    dp[0] = tasks[0].profit;
18
    for (int i = 1; i < n; i++) {
19
      // Why upper bound works?
20
      // [1] if start time i-th task >= end time j-th task, then i-th task can
21
      // complete all previous tasks of j-th task [2] dp[i] can be dp[i-1],
22
      // dp[i] means the maximum profit from 0 to i-th, but it includes i-th
23
      // task or not [3] same end time diffrent profit cases -> because of [2],
24
      // we have to find the last index among duplicate numbers
25
      int j = lastBound(i - 1, tasks, tasks[i].start);
26
      dp[i] = max(dp[i - 1], (j != -1 ? dp[j] : 0) + tasks[i].profit);
27
    }
28
    return dp[n - 1];
29
  }
30
  // Time : O(Nlog(N) + Nlog(N))
31
  // Space : O(N)
32
  // lastBound from upperBound
33
  int lastBound(int end, vector<Task> &tasks, int target) {
34
    int lo = 0, hi = end;
35
    while (lo < hi) {
36
      int m = lo + (hi - lo) / 2;
37
      if (tasks[m].end <= target)
38
        lo = m + 1;
39
      else
40
        hi = m;
41
    }
42
    if (tasks[lo].end > target) lo--;
43
    return lo;
44
  }
45
};