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.
In this approach, the idea is to use dynamic programming by first sorting the offers based on the end house. This allows us to efficiently determine the maximum profit that can be accumulated at each step by either including the current offer or excluding it, and fetching previously computed values that do not overlap.
This C implementation starts by defining a structure for offers and uses qsort to sort offers by their end house. It applies dynamic programming to compute the maximum gold possible up to each offer. The binary_search function is used to find the last non-overlapping offer efficiently, which allows recalculating the maximum gold while considering overlaps optimally.
Time Complexity: O(m log(m)) due to sorting and binary search for each offer.
Space Complexity: O(m) for the dynamic programming array, where m is the number of offers.
In this approach, the offers are first sorted based on their starting and then by ending points. We maintain a map to store the maximum profit ending at a particular house number. This method achieves an optimal solution by always considering the highest profit path to end at any offer's end point strategically.
This C code utilizes a greedy strategy combined with sorting and a mapping array to track maximum profits ending at various positions. After sorting, the solution iterates through each offer while updating the map for each house in the range of current offer, maintaining an optimal solution dynamically without re-evaluating overlapping offers that don’t benefit the profit margin.
Time Complexity: O(m log(m) + n), primarily due to sorting and iterating through offers.
Space Complexity: O(n) for the map array.
We sort all the purchase offers by end in ascending order, and then use dynamic programming to solve the problem.
Define f[i] to represent the maximum amount of gold we can get from the first i purchase offers. The answer is f[n].
For f[i], we can choose not to sell the ith purchase offer, in which case f[i] = f[i - 1]; or we can choose to sell the ith purchase offer, in which case f[i] = f[j] + gold_i, where j is the largest index that satisfies end_j leq start_i.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the number of purchase offers.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sorting | Time Complexity: O(m log(m)) due to sorting and binary search for each offer. |
| Greedy Approach with Sorting and Mapping | Time Complexity: O(m log(m) + n), primarily due to sorting and iterating through offers. |
| Sorting + Binary Search + Dynamic Programming | — |
| 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 |
Maximize the profit as the Salesman | LeetCode Weekly 359 | DP + Binary Search • Anu Sharma • 3,697 views views
Watch 9 more video solutions →Practice Maximize the Profit as the Salesman with our built-in code editor and test cases.
Practice on FleetCode