# Maximize the Profit as the Salesman
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-the-profit-as-the-salesman)
Canonical: https://scaleengineer.com/dsa/problems/maximize-the-profit-as-the-salesman
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## Problem
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`

# Approaches
## Top-Down Dynamic Programming on Offers
This problem can be modeled as a variation of the classic Weighted Interval Scheduling problem. We want to select a subset of non-overlapping "offers" (intervals) to maximize the total "gold" (weight). A natural way to approach this is using recursion with memoization. We first sort the offers by their start house. Then, for each offer, we decide whether to take it or not, and use memoization to store the results of subproblems to avoid redundant calculations.
**Time:** O(m log m), where `m` is the number of offers. Sorting the offers takes `O(m log m)`. The recursive function `findMaxProfit` is called for each of the `m` indices once. Inside each call, we perform a binary search which takes `O(log m)`. Thus, the dynamic programming part also takes `O(m log m)`. · **Space:** O(m), where `m` is the number of offers. This space is used for the recursion stack depth and the memoization array.
**Pros:** It's a direct and intuitive translation of the problem's recursive structure.; It can be more memory-efficient than the `O(n+m)` approach if `n` is significantly larger than `m`.
**Cons:** Generally slower than the linear time DP approach due to the `log m` factor from sorting and binary search.; A deep recursion might lead to a stack overflow for a very large number of offers, though the given constraints should be manageable.
### Explanation
In this top-down dynamic programming approach, we make a decision for each offer: either include it in our set of sales or skip it.

If we decide to take the current offer `i`, we gain its `gold` and must then find the maximum profit from subsequent offers that do not overlap with offer `i`. An offer `j` does not overlap if its `start` house is greater than the `end` house of offer `i`.

If we decide not to take offer `i`, we simply move on to the next offer `i+1` and find the maximum profit from there.

The maximum profit for a state defined by `offer i` is the maximum of these two choices. To make this efficient, we sort the offers by their `start` house. This allows us to quickly find the next non-overlapping offer using binary search. We use a memoization table (an array `memo`) to store the results of `solve(i)` to prevent re-computation.

```java
import java.util.Collections;
import java.util.List;
import java.util.Arrays;

class Solution {
    private int[] memo;
    private List<List<Integer>> offers;
    private int m;

    public int maximizeTheProfit(int n, List<List<Integer>> offersList) {
        this.m = offersList.size();
        this.offers = offersList;
        // Sort offers by start time to enable binary search for the next non-overlapping offer.
        Collections.sort(this.offers, (a, b) -> a.get(0) - b.get(0));
        
        this.memo = new int[m];
        Arrays.fill(memo, -1);
        
        return findMaxProfit(0);
    }

    private int findMaxProfit(int index) {
        if (index >= m) {
            return 0;
        }
        if (memo[index] != -1) {
            return memo[index];
        }

        // Option 1: Don't take the current offer.
        int profit1 = findMaxProfit(index + 1);

        // Option 2: Take the current offer.
        int currentEnd = offers.get(index).get(1);
        int currentGold = offers.get(index).get(2);
        
        // Find the next non-overlapping offer using binary search.
        int nextIndex = findNextOffer(index + 1, currentEnd);
        
        int profit2 = currentGold + findMaxProfit(nextIndex);

        memo[index] = Math.max(profit1, profit2);
        return memo[index];
    }

    // Finds the first offer starting after targetEnd.
    private int findNextOffer(int left, int targetEnd) {
        int right = m - 1;
        int nextIndex = m;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (offers.get(mid).get(0) > targetEnd) {
                nextIndex = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            } 
        }
        return nextIndex;
    }
}
```
### Algorithm
- Sort the `offers` array based on the `start` house number.
- Create a memoization array `memo` of size `m` (number of offers), initialized to a value indicating it's not computed (e.g., -1).
- Implement a recursive function `solve(index)`:
  - **Base Case:** If `index` is greater than or equal to the number of offers, return 0.
  - **Memoization Check:** If `memo[index]` has been computed, return the stored value.
  - **Choice 1 (Skip offer `index`):** The profit is `solve(index + 1)`.
  - **Choice 2 (Take offer `index`):** 
    - Let the current offer be `[start, end, gold]`.
    - Find the index `j` of the first offer whose `start` is greater than the current offer's `end`. This can be done efficiently using binary search on the sorted `offers` array.
    - The profit for this choice is `gold + solve(j)`.
  - **Result:** Store and return the maximum of the profits from Choice 1 and Choice 2 in `memo[index]`.
- The initial call to start the process is `solve(0)`.

## Bottom-Up Dynamic Programming on Houses
A more efficient approach involves using dynamic programming on the houses themselves. We define `dp[i]` as the maximum profit that can be obtained by considering houses from `0` to `i-1`. We iterate from house `0` to `n-1`, and at each house `i`, we calculate the maximum profit we can make by either not selling house `i` or selling it as part of an offer that ends at `i`. This avoids sorting and leads to a linear time solution.
**Time:** O(n + m), where `n` is the number of houses and `m` is the number of offers. It takes `O(m)` to group offers by their end point. The DP calculation involves a single loop from `1` to `n`. Inside the loop, we iterate over offers ending at the current house. Since each offer is processed exactly once across all iterations, the total time for the DP part is `O(n + m)`. · **Space:** O(n + m), where `n` is the number of houses and `m` is the number of offers. `O(n)` space is required for the `dp` array, and `O(m)` space is needed to store the grouped offers in `offersByEnd`.
**Pros:** Asymptotically the most efficient solution with linear time complexity.; It is generally faster in practice for the given constraints compared to the `O(m log m)` approach.
**Cons:** Requires space proportional to `n + m`, which might be large if `n` is very large, potentially leading to memory issues.
### Explanation
This bottom-up dynamic programming approach builds the solution iteratively. The state `dp[i]` represents the maximum profit from houses `0` to `i-1`.

The state transition is based on the choices at each house `i-1`:
1.  **Don't take an offer ending at `i-1`**: The maximum profit is simply the profit from houses `0` to `i-2`, which is `dp[i-1]`.
2.  **Take an offer ending at `i-1`**: If we accept an offer `[start, i-1, gold]`, the total profit is the `gold` from this offer plus the maximum profit achievable up to house `start-1`, which is stored in `dp[start]`.

We must consider all offers ending at `i-1` and choose the one that maximizes the profit. To do this efficiently, we first preprocess the `offers` list into a structure that groups offers by their `end` house. This allows for quick lookups.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        // Group offers by their end house for efficient lookup.
        List<List<int[]>> offersByEnd = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            offersByEnd.add(new ArrayList<>());
        }
        for (List<Integer> offer : offers) {
            // offer is [start, end, gold]
            // We store [start, gold] at index `end`.
            offersByEnd.get(offer.get(1)).add(new int[]{offer.get(0), offer.get(2)});
        }

        // dp[i] = max profit considering houses 0 to i-1.
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            // The current house being considered is i-1.
            
            // Option 1: Don't take any offer ending at i-1.
            // The profit is the max profit from houses 0 to i-2.
            dp[i] = dp[i-1];

            // Option 2: Take an offer ending at i-1.
            int endHouse = i - 1;
            if (!offersByEnd.get(endHouse).isEmpty()) {
                for (int[] offerDetails : offersByEnd.get(endHouse)) {
                    int start = offerDetails[0];
                    int gold = offerDetails[1];
                    // Profit from this offer + max profit before this offer starts.
                    // dp[start] is max profit from houses 0..start-1.
                    int profitWithThisOffer = dp[start] + gold;
                    dp[i] = Math.max(dp[i], profitWithThisOffer);
                }
            }
        }

        return dp[n];
    }
}
```
### Algorithm
- Create a data structure, `offersByEnd`, to group offers by their `end` house. An array of lists is suitable, where `offersByEnd[i]` stores all offers ending at house `i`.
- Initialize a DP array `dp` of size `n + 1` with zeros. `dp[i]` will store the maximum profit considering houses from `0` to `i-1`.
- Iterate from `i = 1` to `n`:
  - **Step 1:** Set `dp[i] = dp[i-1]`. This handles the case where no offer ending at house `i-1` is taken, carrying over the maximum profit from the previous state.
  - **Step 2:** Check for offers ending at house `i-1` in `offersByEnd[i-1]`.
  - For each offer `[start, i-1, gold]` found:
    - Calculate the potential profit if this offer is taken: `dp[start] + gold`. This combines the offer's gold with the maximum profit achievable before this offer's range.
    - Update `dp[i]` with the maximum value found so far: `dp[i] = max(dp[i], dp[start] + gold)`.
- The final answer is `dp[n]`, which represents the maximum profit considering all houses up to `n-1`.

# Solutions
### Java

```java
class Solution {
public
  int maximizeTheProfit(int n, List<List<Integer>> offers) {
    offers.sort((a, b)->a.get(1) - b.get(1));
    n = offers.size();
    int[] f = new int[n + 1];
    int[] g = new int[n];
    for (int i = 0; i < n; ++i) {
      g[i] = offers.get(i).get(1);
    }
    for (int i = 1; i <= n; ++i) {
      var o = offers.get(i - 1);
      int j = search(g, o.get(0));
      f[i] = Math.max(f[i - 1], f[j] + o.get(2));
    }
    return f[n];
  }
private
  int search(int[] nums, int x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximizeTheProfit(int n, vector<vector<int>> &offers) {
    sort(
        offers.begin(), offers.end(),
        [](const vector<int> &a, const vector<int> &b) { return a[1] < b[1]; });
    n = offers.size();
    vector<int> f(n + 1);
    vector<int> g;
    for (auto &o : offers) {
      g.push_back(o[1]);
    }
    for (int i = 1; i <= n; ++i) {
      auto o = offers[i - 1];
      int j = lower_bound(g.begin(), g.end(), o[0]) - g.begin();
      f[i] = max(f[i - 1], f[j] + o[2]);
    }
    return f[n];
  }
};

```

### Python

```python
class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int: offers . sort(key=lambda x: x[1]) f = [0] * (len(offers) + 1) g = [x[1] for x in offers] for i, (s, _, v) in enumerate(offers, 1): j = bisect_left(g, s) f[i] = max(f[i - 1], f[j] + v) return f[- 1]

```