We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximize the Profit as the Salesman

Difficulty: Medium

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 for gold_i 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.

Key Insights

  • The problem can be approached using dynamic programming to keep track of the maximum gold earned by considering each house.
  • Each offer has a range of houses that must be sold together, creating a potential overlap between offers.
  • We need to ensure that houses sold are not counted more than once for different buyers.
  • The solution involves sorting offers by their end house index and using a DP array to store the maximum gold earned up to each house.

Space and Time Complexity

Time Complexity: O(m log m + n) where m is the number of offers due to sorting and n is the traversal of houses. Space Complexity: O(n) for the DP array.

Solution

To solve this problem, we will:

  1. Sort the offers based on the end index.
  2. Use a dynamic programming approach where dp[i] represents the maximum gold earned by selling houses from 0 to i.
  3. For each offer, check if the houses can be sold without overlapping with previously accepted offers and update the dp array accordingly.

Code Solutions

def maximizeGold(n, offers):
    # Sort offers by the end index
    offers.sort(key=lambda x: x[1])
    
    # Initialize a dp array
    dp = [0] * n
    offer_index = 0
    
    for i in range(n):
        # Carry forward the previous maximum if no offer is taken
        if i > 0:
            dp[i] = dp[i - 1]
        
        # Process all offers that end at the current index
        while offer_index < len(offers) and offers[offer_index][1] == i:
            start, end, gold = offers[offer_index]
            # Calculate the potential new gold amount
            new_gold = gold + (dp[start - 1] if start > 0 else 0)
            # Update dp[i] with the maximum gold possible
            dp[i] = max(dp[i], new_gold)
            offer_index += 1
            
    return dp[n - 1]
← Back to All Questions