Maximize the Profit as the Salesman Interview Question for Amazon

# Maximum Gold Earned by Selling Houses

## Problem Description

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] = [start_i, end_i, gold_i]`, indicating that the `i`-th buyer wants to buy all the houses from `start_i` to `end_i` (inclusive) for `gold_i` amount of gold. As a salesman, your goal is to **maximize** your earnings by strategically selecting and selling houses to buyers. Note that different buyers can't buy the same house, and some houses may remain unsold.

Return the maximum amount of gold you can earn.

**Example 1:**

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:**

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.


## Naive Solution (Brute Force)

The most straightforward approach is to consider all possible combinations of offers and calculate the total gold earned for each combination.  We need to ensure that no two selected offers overlap.  This can be done by generating all possible subsets of the `offers` array and checking for overlaps within each subset. If there are no overlaps, we calculate the total gold and update the maximum gold earned so far.

This approach has exponential time complexity, making it highly inefficient for larger inputs.

## Optimal Solution (Dynamic Programming)

We can solve this problem efficiently using dynamic programming. The core idea is to sort the offers based on their end indices.  Then, for each offer, we either include it in our selection or exclude it.  If we include the offer, we need to find the latest non-overlapping offer that comes before it.  We can use binary search to find this non-overlapping offer.

Here's a step-by-step breakdown:

1.  **Sort Offers:** Sort the `offers` array based on the end indices in ascending order. This allows us to process offers in a way that facilitates dynamic programming.
2.  **DP Array:** Create a `dp` array where `dp[i]` represents the maximum gold we can earn by considering the first `i` offers.
3.  **Base Case:** `dp[0] = 0` (no offers, no gold).
4.  **Iteration:** For each offer `i` from `1` to `offers.length`:
    *   **Exclude Offer:** `dp[i] = dp[i-1]` (we don't include the current offer, so the maximum gold remains the same as the previous offer).
    *   **Include Offer:** Find the latest non-overlapping offer `j` before offer `i`. If no such offer exists, `j = 0`. Calculate the gold earned by including the current offer: `gold_i + dp[j]`. Update `dp[i]` with the maximum of `dp[i-1]` and `gold_i + dp[j]`.
5.  **Result:** The final result is `dp[offers.length]`.  This will contain the maximized gold after considering all the offers.

```python
def max_gold(n: int, offers: list[list[int]]) -> int:
    offers.sort(key=lambda x: x[1])  # Sort by end indices
    dp = [0] * (len(offers) + 1)

    for i in range(1, len(offers) + 1):
        start, end, gold = offers[i - 1]
        
        # Exclude the current offer
        dp[i] = dp[i - 1]
        
        # Include the current offer
        j = find_latest_non_overlapping_offer(offers, i - 1)
        if j != -1:
            dp[i] = max(dp[i], gold + dp[j + 1])
        else:
            dp[i] = max(dp[i], gold)

    return dp[len(offers)]


def find_latest_non_overlapping_offer(offers: list[list[int]], current_index: int) -> int:
    # Binary search to find the latest non-overlapping offer
    low = 0
    high = current_index - 1
    latest_non_overlapping = -1
    
    while low <= high:
        mid = (low + high) // 2
        if offers[mid][1] < offers[current_index][0]:
            latest_non_overlapping = mid
            low = mid + 1
        else:
            high = mid - 1
            
    return latest_non_overlapping

# Example usage:
n = 5
offers1 = [[0, 0, 1], [0, 2, 2], [1, 3, 2]]
print(f"Maximum gold for offers1: {max_gold(n, offers1)}")  # Output: 3

offers2 = [[0, 0, 1], [0, 2, 10], [1, 3, 2]]
print(f"Maximum gold for offers2: {max_gold(n, offers2)}")  # Output: 10

Big(O) Run-time Analysis

Sorting Offers: Sorting the offers array takes O(N log N) time, where N is the number of offers. This is because we're using a comparison-based sorting algorithm (like mergesort or quicksort).
Dynamic Programming Loop: The main loop iterates through each offer once, taking O(N) time.
Binary Search: Inside the loop, we perform a binary search to find the latest non-overlapping offer. Binary search takes O(log N) time.

Therefore, the overall time complexity is O(N log N) + O(N log N) which simplifies to O(N log N).

Big(O) Space Usage Analysis

DP Array: The dp array stores the maximum gold earned for each prefix of offers. It has a size of N+1, where N is the number of offers, resulting in O(N) space.

Therefore, the overall space complexity is O(N).

Edge Cases and Handling

Empty Offers Array: If the offers array is empty, the maximum gold earned is 0. The provided solution handles this case correctly because the loop won't execute, and the initial value of dp[0] (which is 0) will be returned.
Overlapping Offers Only: If all offers overlap with each other, the algorithm will choose the single best offer, resulting in the maximum possible gold in this scenario.
Offers with Identical End Times: If there are offers with identical end times, the sorting algorithm will maintain the relative order of these offers. The dynamic programming approach will still correctly consider all possible combinations and find the optimal solution.
Large Number of Offers: For a very large number of offers (close to the constraint limit), the O(N log N) time complexity might become a bottleneck. However, with reasonable constraints (up to 10^5), the algorithm should still perform efficiently.
All offers giving 0 gold: The algorithm correctly returns 0 gold in the dp array.