Skip to content

1235. Maximum Profit in Job Scheduling 👍

Approach 1: Top-down

  • Time: $O(\texttt{sort})$
  • 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
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();
    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, [](const Job& a, const Job& b) {
      return 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:
  // 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>& A, int startFrom, int target) {
    return lower_bound(A.begin() + startFrom, A.end(), target) - A.begin();
  }
};

 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
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;
    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) -> 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 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[] 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
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)

Approach 2: Bottom-up

  • Time: $O(\texttt{sort})$
  • 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
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] := the maximum profit to schedule jobs[i..n)
    vector<int> dp(n + 1);
    vector<Job> jobs;

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

    ranges::sort(jobs, [](const Job& a, const Job& b) {
      return a.startTime < b.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 pick = jobs[i].profit + dp[j];
      const int skip = dp[i + 1];
      dp[i] = max(pick, skip);
    }

    return dp[0];
  }

  int firstGreaterEqual(const vector<int>& A, int startFrom, int target) {
    return lower_bound(A.begin() + startFrom, A.end(), target) - A.begin();
  }
};

 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
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] := the maximum profit to schedule jobs[i..n)
    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);

    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 pick = jobs[i].profit + dp[j];
      final int skip = dp[i + 1];
      dp[i] = Math.max(pick, 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
class Solution:
  def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
    # dp[i] := the maximum profit to schedule jobs[i..n)
    dp = [0] * (len(startTime) + 1)
    jobs = sorted([(s, e, p) for s, e, p in zip(startTime, endTime, profit)])

    for i in range(len(startTime)):
      startTime[i] = jobs[i][0]

    for i in reversed(range(len(startTime))):
      j = bisect.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(\texttt{sort})$
  • 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]);

    ranges::sort(jobs, [](const Job& a, const Job& 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))