Skip to content

2830. Maximize the Profit as the Salesman 👍

  • Time: $O(n + |\texttt{offers}|)$
  • Space: $O(n + |\texttt{offers}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int maximizeTheProfit(int n, vector<vector<int>>& offers) {
    // dp[i] := the maximum amount of gold of selling the first i houses
    vector<int> dp(n + 1);
    vector<vector<pair<int, int>>> endToStartAndGolds(n);

    for (const vector<int>& offer : offers) {
      const int start = offer[0];
      const int end = offer[1];
      const int gold = offer[2];
      endToStartAndGolds[end].emplace_back(start, gold);
    }

    for (int end = 1; end <= n; ++end) {
      // Get at least the same gold as selling the first `end - 1` houses.
      dp[end] = dp[end - 1];
      for (const auto& [start, gold] : endToStartAndGolds[end - 1])
        dp[end] = max(dp[end], dp[start] + gold);
    }

    return dp[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
class Solution {
  public int maximizeTheProfit(int n, List<List<Integer>> offers) {
    // dp[i] := the maximum amount of gold of selling the first i houses
    int[] dp = new int[n + 1];
    List<Pair<Integer, Integer>>[] endToStartAndGolds = new List[n];

    for (int i = 0; i < n; ++i)
      endToStartAndGolds[i] = new ArrayList<>();

    for (List<Integer> offer : offers) {
      final int start = offer.get(0);
      final int end = offer.get(1);
      final int gold = offer.get(2);
      endToStartAndGolds[end].add(new Pair<>(start, gold));
    }

    for (int end = 1; end <= n; ++end) {
      // Get at least the same gold as selling the first `end - 1` houses.
      dp[end] = dp[end - 1];
      for (Pair<Integer, Integer> pair : endToStartAndGolds[end - 1]) {
        final Integer start = pair.getKey();
        final Integer gold = pair.getValue();
        dp[end] = Math.max(dp[end], dp[start] + gold);
      }
    }

    return dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def maximizeTheProfit(self, n: int, offers: list[list[int]]) -> int:
    # dp[i] := the maximum amount of gold of selling the first i houses
    dp = [0] * (n + 1)
    endToStartAndGolds = [[] for _ in range(n)]

    for start, end, gold in offers:
      endToStartAndGolds[end].append((start, gold))

    for end in range(1, n + 1):
      # Get at least the same gold as selling the first `end - 1` houses.
      dp[end] = dp[end - 1]
      for start, gold in endToStartAndGolds[end - 1]:
        dp[end] = max(dp[end], dp[start] + gold)

    return dp[n]