2830. Maximize the Profit as the Salesman LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2830. Maximize the Profit as the Salesman LeetCode Solution with the best time and space complexity. The solution to Maximize the Profit as the Salesman 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
Maximize the Profit as the Salesman solution in C++
Maximize the Profit as the Salesman solution in Java
Maximize the Profit as the Salesman solution in Python
Additional Resources

2830. Maximize the Profit as the Salesman LeetCode Solution image

Problem Statement of Maximize the Profit as the Salesman

You are given an integer n representing the number of houses on a number line, numbered from 0 to n – 1.
Additionally, you are given a 2D integer array offers where offers[i] = [starti, endi, goldi], indicating that ith buyer wants to buy all the houses from starti to endi for goldi amount of gold.
As a salesman, your goal is to maximize your earnings by strategically selecting and selling houses to buyers.
Return the maximum amount of gold you can earn.
Note that different buyers can’t buy the same house, and some houses may remain unsold.

Example 1:

Input: n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
Output: 3
Explanation: There are 5 houses numbered from 0 to 4 and there are 3 purchase offers.
We sell houses in the range [0,0] to 1st buyer for 1 gold and houses in the range [1,3] to 3rd buyer for 2 golds.
It can be proven that 3 is the maximum amount of gold we can achieve.

Example 2:

Input: n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]
Output: 10
Explanation: There are 5 houses numbered from 0 to 4 and there are 3 purchase offers.
We sell houses in the range [0,2] to 2nd buyer for 10 golds.
It can be proven that 10 is the maximum amount of gold we can achieve.

Constraints:

1 <= n <= 105
1 <= offers.length <= 105
offers[i].length == 3
0 <= starti <= endi <= n – 1
1 <= goldi <= 103

Complexity Analysis

Time Complexity: O(n + |\texttt{offers}|)
Space Complexity: O(n + |\texttt{offers}|)

2830. Maximize the Profit as the Salesman LeetCode Solution in C++

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];
  }
};
/* code provided by PROGIEZ */

2830. Maximize the Profit as the Salesman LeetCode Solution in Java

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];
  }
}
// code provided by PROGIEZ

2830. Maximize the Profit as the Salesman LeetCode Solution in Python

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]
 # code by PROGIEZ

Additional Resources

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

Table of Contents