Watch 10 video solutions for Maximize the Profit as the Salesman, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by Anu Sharma has 3,697 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1051 <= offers.length <= 105offers[i].length == 30 <= starti <= endi <= n - 11 <= goldi <= 103Problem Overview: You receive multiple offers where each offer buys a range of houses [start, end] for a given profit. Only one offer can use a house at a time, so overlapping ranges cannot both be accepted. The goal is to pick a set of non-overlapping offers that maximizes total profit.
Approach 1: Dynamic Programming with Sorting and Binary Search (O(m log m) time, O(m) space)
This problem is a classic weighted interval scheduling variant. Start by sorting all offers by their ending house. Define dp[i] as the maximum profit achievable considering the first i offers. For each offer, you decide whether to skip it or include it. If you include it, you must find the last offer that ends before the current offer's start. Because the offers are sorted by end time, you can locate that previous compatible offer using binary search. The transition becomes dp[i] = max(dp[i-1], profit[i] + dp[lastNonOverlap]). Sorting plus binary search makes the lookup efficient while dynamic programming accumulates the best profit.
This method works well when the number of offers is large because it avoids scanning all previous offers for each decision. The combination of sorting, binary search, and dynamic programming guarantees an optimal solution.
Approach 2: Greedy-Style Dynamic Programming with Sorting and Mapping (O(n + m log m) time, O(n + m) space)
Another efficient strategy organizes offers by their ending house. First sort the offers by end index, then group them using a hash map or adjacency list keyed by the ending house. Create a DP array where dp[i] represents the maximum profit achievable considering houses up to i. For each house index, carry forward the previous best value dp[i] = dp[i-1]. Then process every offer that ends at i and evaluate whether taking it increases profit using dp[start] + profit. This approach treats the houses as the main iteration axis while evaluating all offers that finish at that position.
The key insight is that the optimal solution up to a house only depends on earlier houses. Mapping offers by end position prevents repeatedly scanning the entire list of offers. The algorithm relies on efficient indexing within an array and incremental dynamic programming updates.
Recommended for interviews: The dynamic programming solution with sorting and binary search is the most commonly expected answer. It directly models the problem as weighted interval scheduling and demonstrates strong understanding of DP state transitions and binary search optimization. The mapping-based DP is also solid and often easier to implement when the house count n is moderate.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming + Sorting + Binary Search | O(m log m) | O(m) | Best general solution for large offer lists; classic weighted interval scheduling approach |
| Greedy-Style DP with Sorting and Offer Mapping | O(n + m log m) | O(n + m) | When iterating directly across houses is simpler and house count n is manageable |