Scale Engineer

Maximize the Profit as the Salesman

Med
#2530Time: 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.
Patterns
Dynamic Programming
Algorithms
Binary SearchSorting
Data structures
ArrayHash Table

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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).

Walkthrough

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.

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem