Maximize the Profit as the Salesman — Problem & Solution
Maximize the Profit as the Salesman solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximize the Profit as the Salesman is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Sorting, Binary Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There are n houses on a street, numbered 0 to n - 1. As a salesman you receive offers offers[i] = [start_i, end_i, gold_i]: buyer i wants every house from start_i to end_i inclusive and will pay gold_i for them.
Each house can be sold to at most one buyer, and some houses may stay unsold. Choose which offers to accept to maximise the total gold, and return that maximum.
Example 1
Input: n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
Output: 3
Explanation: Accept `[0,0,1]` and `[1,3,2]`.
Example 2
Input: n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]
Output: 10
Example 3
Input: n = 4, offers = [[0,1,5],[2,3,5],[1,2,9]]
Output: 10
Explanation: The two outer offers (5 + 5) beat the middle one (9).
Constraints
1 <= n <= 10^51 <= offers.length <= 10^5offers[i].length == 30 <= start_i <= end_i <= n - 11 <= gold_i <= 10^3
Hints for Maximize the Profit as the Salesman
Hint 1
This is weighted interval scheduling: pick non-overlapping intervals of maximum total weight.
Hint 2
Let
dp[i]be the best gold using only houses0..i-1.Hint 3
dp[i + 1] = max(dp[i], dp[start] + gold)over every offer whoseendisi.
How to solve Maximize the Profit as the Salesman
Sweep houses left to right. The best profit over the first e + 1 houses either leaves house e unsold or sells it as the last house of some offer [s, e, g], whose earlier houses are an independent prefix problem.
Approach
- Group (or sort) the offers by their end house.
dp[0] = 0. Fore = 0..n-1:dp[e + 1] = dp[e], then for each offer[s, e, g]:dp[e + 1] = max(dp[e + 1], dp[s] + g).- Return
dp[n].
Why it works
In any valid choice of offers over houses 0..e, either no accepted offer covers house e (the value is at most dp[e]), or exactly one accepted offer ends at e and all others lie in houses 0..s-1, worth at most dp[s]. Both cases are covered, so by induction dp is optimal.
Complexity
- Time —
O(n + m log m) for m offers - Space —
O(n + m)
Pitfalls
- Offers that share a house conflict — the next offer must start strictly after the previous one's end (
dp[s]covers houses0..s-1). - Several offers can end at the same house; consider all of them.
- Houses may remain unsold, so carry
dp[e]forward.
Reference solution
Python
from typing import List
def maximizeTheProfit(n: int, offers: List[List[int]]) -> int:
ending = [[] for _ in range(n)]
for s, e, g in offers:
ending[e].append((s, g))
dp = [0] * (n + 1)
for e in range(n):
best = dp[e]
for s, g in ending[e]:
if dp[s] + g > best:
best = dp[s] + g
dp[e + 1] = best
return dp[n]Java
public static int maximizeTheProfit(int n, int[][] offers) {
int[][] os = offers.clone();
Arrays.sort(os, (a, b) -> Integer.compare(a[1], b[1]));
int[] dp = new int[n + 1];
int ptr = 0;
for (int e = 0; e < n; e++) {
dp[e + 1] = dp[e];
while (ptr < os.length && os[ptr][1] == e) {
dp[e + 1] = Math.max(dp[e + 1], dp[os[ptr][0]] + os[ptr][2]);
ptr++;
}
}
return dp[n];
}C++
int maximizeTheProfit(int n, vector<vector<int>>& offers) {
vector<vector<int>> os(offers.begin(), offers.end());
sort(os.begin(), os.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });
vector<int> dp(n + 1, 0);
size_t ptr = 0;
for (int e = 0; e < n; e++) {
dp[e + 1] = dp[e];
while (ptr < os.size() && os[ptr][1] == e) {
dp[e + 1] = max(dp[e + 1], dp[os[ptr][0]] + os[ptr][2]);
ptr++;
}
}
return dp[n];
}JavaScript
var maximizeTheProfit = function(n, offers) {
var os = offers.slice().sort(function(a, b) { return a[1] - b[1]; });
var dp = new Array(n + 1).fill(0);
var ptr = 0;
for (var e = 0; e < n; e++) {
dp[e + 1] = dp[e];
while (ptr < os.length && os[ptr][1] === e) {
var cand = dp[os[ptr][0]] + os[ptr][2];
if (cand > dp[e + 1]) dp[e + 1] = cand;
ptr++;
}
}
return dp[n];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming