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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize the Profit as the Salesman

Number: 2979

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

You are given n houses on a number line (numbered 0 to n-1) and an array of offers where each offer is defined by [start, end, gold]. An offer indicates that a buyer is willing to purchase all houses from start to end (inclusive) for a specified amount of gold. The challenge is to sell the houses to maximize total profit under the constraint that a house can only be sold once (i.e., offers must not overlap in terms of houses sold).

Key Insights

  • This is a weighted interval scheduling problem.
  • Each offer is an interval with an associated profit (gold).
  • To avoid conflicts (overlapping intervals), we select non-overlapping intervals that maximize the sum of gold.
  • Sorting the offers (or processing houses in order) allows a dynamic programming approach where for each house you decide whether to take an offer ending at that house.
  • Using a DP array that iterates through house indices and updates profits based on valid offers helps in building the optimal solution.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of houses and m is the number of offers
Space Complexity: O(n + m) for the DP array and the mapping of offers to their ending houses

Solution

We solve the problem using dynamic programming by iterating through each house from 0 to n-1. A helper structure (e.g. an array of lists) is used to group offers by their ending house. For each house, we update our DP state as follows:

  1. Inherit the maximum profit from the previous house (i.e., not selling any house at the current index).
  2. For each offer ending at the current house, consider using that offer by adding its profit to the profit accumulated up to the start of the offer (or 0 if the offer starts at 0).
  3. Update the DP state at the current house with the maximum value between the inherited profit and the newly computed profit. This method ensures that the offers do not overlap and that we maximize the overall profit.

Code Solutions

# Function to maximize the profit given number of houses and offers.
import collections

def maximizeTheProfit(n, offers):
    # Group offers by their ending house.
    offers_by_end = collections.defaultdict(list)
    for start, end, gold in offers:
        offers_by_end[end].append((start, gold))
    
    # dp[i] represents the maximum profit achievable using houses 0 to i.
    dp = [0] * n
    for house in range(n):
        # Carry forward the maximum profit from the previous house.
        if house > 0:
            dp[house] = dp[house - 1]
        # Process each offer ending at the current house.
        for start, gold in offers_by_end.get(house, []):
            profit = (dp[start - 1] if start > 0 else 0) + gold
            dp[house] = max(dp[house], profit)
    return dp[n - 1]

# Example usage:
if __name__ == "__main__":
    n = 5
    offers = [[0, 0, 1], [0, 2, 10], [1, 3, 2]]
    print(maximizeTheProfit(n, offers))  # Expected output: 10
← Back to All Questions