Maximize the Profit as the Salesman solution and explanation
9 more videos on this problem
Maximize the profit as the Salesman | LeetCode Weekly 359 | DP + Binary SearchAnu Sharma · 15:43 · 3K views
Leetcode Weekly contest 359 - Medium- Maximize the Profit as the SalesmanPrakhar Agrawal · 11:42 · 2K views
Leetcode 2830 Maximize the Profit as the Salesman HindiThinkCode · 12:42 · 1K views
2830. Maximize the Profit as the SalesmanAyush Rao · 8:02 · 1K views
2830. Maximize the Profit as the Salesman (Leetcode Medium)Programming Live with Larry · 13:19 · 1K views
2830. Maximize the Profit as the Salesman | Weekly Leetcode 359codingMohan · 20:51 · 1K views
Maximize the Profit as the Salesman - LEETCODE WEEKLY CONTEST 359 (Explanation in details)Joyjit Codes · 10:00 · 782 views
Leetcode Weekly Contest 359 | Maximize the Profit as the Salesman | Hindi ExplanationPawan Kumar Giri · 20:40 · 775 views
maximize the profit as the salesman #leetcodechallenge #leetcodecrazy developers · 0:31 · 454 views
【每日一题】LeetCode 2830. Maximize the Profit as the SalesmanHuifeng Guan · 12:10 · 416 views
The problem
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 <= 103
Approach overview
Problem 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 1: Dynamic Programming with Sorting
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.
from typing import List, Tuple
def maximize_profit(n: int, offers: List[Tuple[int, int, int]]) -> int:
offers.sort(key=lambda x: x[1])
dp = [0] * len(offers)
dp[0] = offers[0][2]
def binary_search(target):
low, high = 0, len(offers) - 1
while low <= high:
mid = (low + high) // 2
if offers[mid][1] < target:
low = mid + 1
else:
high = mid - 1
return high
for i in range(1, len(offers)):
include_profit = offers[i][2]
last_non_conflicting = binary_search(offers[i][0])
if last_non_conflicting != -1:
include_profit += dp[last_non_conflicting]
dp[i] = max(dp[i - 1], include_profit)
return dp[-1]
if __name__ == "__main__":
offers = [(0, 0, 1), (0, 2, 2), (1, 3, 2)]
n = 5
print(maximize_profit(n, offers))import java.util.*;
class Offer {
int start, end, gold;
Offer(int start, int end, int gold) {
this.start = start;
this.end = end;
this.gold = gold;
}
}
public class MaximizeProfit {
public static int maximizeProfit(int n, Offer[] offers) {
Arrays.sort(offers, Comparator.comparingInt(o -> o.end));
int[] dp = new int[offers.length];
dp[0] = offers[0].gold;
for (int i = 1; i < offers.length; i++) {
int includeProfit = offers[i].gold;
int lastNonConflictingIndex = binarySearch(offers, i);
if (lastNonConflictingIndex != -1) {
includeProfit += dp[lastNonConflictingIndex];
}
dp[i] = Math.max(dp[i - 1], includeProfit);
}
return dp[dp.length - 1];
}
private static int binarySearch(Offer[] offers, int index) {
int low = 0, high = index - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (offers[mid].end < offers[index].start) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
public static void main(String[] args) {
Offer[] offers = {
new Offer(0, 0, 1),
new Offer(0, 2, 2),
new Offer(1, 3, 2)
};
int n = 5;
System.out.println(maximizeProfit(n, offers));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Offer {
int start, end, gold;
};
bool comp(Offer a, Offer b) {
return a.end < b.end;
}
int binarySearch(const vector<Offer>& offers, int target) {
int lo = 0, hi = offers.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (offers[mid].end < target) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return hi;
}
int maximizeProfit(int n, vector<Offer>& offers) {
sort(offers.begin(), offers.end(), comp);
vector<int> dp(offers.size(), 0);
dp[0] = offers[0].gold;
for (int i = 1; i < offers.size(); ++i) {
int includeProfit = offers[i].gold;
int noConflitIdx = binarySearch(offers, offers[i].start);
if (noConflitIdx != -1) {
includeProfit += dp[noConflitIdx];
}
dp[i] = max(dp[i - 1], includeProfit);
}
return dp.back();
}
int main() {
vector<Offer> offers = { {0, 0, 1}, {0, 2, 2}, {1, 3, 2} };
int n = 5;
cout << maximizeProfit(n, offers) << endl;
return 0;
}function maximizeProfit(n, offers) {
offers.sort((a, b) => a[1] - b[1]);
const dp = Array(offers.length).fill(0);
dp[0] = offers[0][2];
function binarySearch(target) {
let low = 0, high = offers.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (offers[mid][1] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
for (let i = 1; i < offers.length; i++) {
let includeProfit = offers[i][2];
let lastNonConflicting = binarySearch(offers[i][0]);
if (lastNonConflicting !== -1) {
includeProfit += dp[lastNonConflicting];
}
dp[i] = Math.max(dp[i - 1], includeProfit);
}
return dp[dp.length - 1];
}
console.log(maximizeProfit(5, [[0, 0, 1], [0, 2, 2], [1, 3, 2]]));#include <stdio.h>
#include <stdlib.h>
typedef struct {
int start;
int end;
int gold;
} Offer;
int compare(const void *a, const void *b) {
return ((Offer *)a)->end - ((Offer *)b)->end;
}
int max(int a, int b) {
return a > b ? a : b;
}
int binary_search(Offer offers[], int high, int target) {
int low = 0, mid;
while (low <= high) {
mid = (low + high) / 2;
if (offers[mid].end < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
int maximizeProfit(int n, Offer offers[], int offersSize) {
qsort(offers, offersSize, sizeof(Offer), compare);
int dp[offersSize];
dp[0] = offers[0].gold;
for (int i = 1; i < offersSize; i++) {
int includeProfit = offers[i].gold;
int lastNonOverlapping = binary_search(offers, i - 1, offers[i].start);
if (lastNonOverlapping != -1) {
includeProfit += dp[lastNonOverlapping];
}
dp[i] = max(dp[i - 1], includeProfit);
}
return dp[offersSize - 1];
}
int main() {
Offer offers[] = { {0, 0, 1}, {0, 2, 2}, {1, 3, 2} };
int n = 5;
int offersSize = sizeof(offers) / sizeof(Offer);
printf("%d\n", maximizeProfit(n, offers, offersSize));
return 0;
}using System;
public struct Offer {
public int Start, End, Gold;
public Offer(int start, int end, int gold) {
Start = start;
End = end;
Gold = gold;
}
}
public class MaximizeProfit {
private static int BinarySearch(Offer[] offers, int target) {
int low = 0, high = offers.Length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (offers[mid].End < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
public static int Maximize(int n, Offer[] offers) {
Array.Sort(offers, (a, b) => a.End.CompareTo(b.End));
int[] dp = new int[offers.Length];
dp[0] = offers[0].Gold;
for (int i = 1; i < offers.Length; i++) {
int includeProfit = offers[i].Gold;
int lastNonConflicting = BinarySearch(offers, offers[i].Start);
if (lastNonConflicting != -1) {
includeProfit += dp[lastNonConflicting];
}
dp[i] = Math.Max(dp[i - 1], includeProfit);
}
return dp[^1];
}
public static void Main() {
Offer[] offers = {
new Offer(0, 0, 1),
new Offer(0, 2, 2),
new Offer(1, 3, 2)
};
int n = 5;
Console.WriteLine(Maximize(n, offers));
}
}The Python implementation sorts the offers list by the end house. It employs a dynamic programming list, dp, to store maximum profit up to each offer. A helper function, binary_search, finds the last non-overlapping offer efficiently. During the iteration, the program considers both including and excluding each offer to compute the optimal profit, using the result of binary search to add the previous non-overlapping profit where possible.
Time Complexity: O(m log(m)), with m indicating the number of offers (due to sorting and binary searching).
Space Complexity: O(m) for the dynamic programming array.
Approach 2: Greedy Approach with Sorting and Mapping
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.
from typing import List, Tuple
def maximize_profit(n: int, offers: List[Tuple[int, int, int]]) -> int:
offers.sort(key=lambda x: (x[0], x[1]))
max_profit = [0] * n
current_max = 0
for start, end, gold in offers:
if start > 0:
gold += max_profit[start - 1]
current_max = max(current_max, gold)
for i in range(start, end + 1):
max_profit[i] = max(max_profit[i], current_max)
return current_max
if __name__ == "__main__":
offers = [(0, 0, 1), (0, 2, 2), (1, 3, 2)]
n = 5
print(maximize_profit(n, offers))import java.util.*;
class Offer {
int start, end, gold;
Offer(int start, int end, int gold) {
this.start = start;
this.end = end;
this.gold = gold;
}
}
public class MaximizeProfit {
public static int maximizeProfit(int n, Offer[] offers) {
Arrays.sort(offers, (a, b) -> (a.start != b.start ? a.start - b.start : a.end - b.end));
int[] maxProfit = new int[n];
int result = 0;
for (Offer offer : offers) {
int currentProfit = offer.gold;
if (offer.start > 0)
currentProfit += maxProfit[offer.start - 1];
result = Math.max(result, currentProfit);
for (int i = offer.start; i <= offer.end; i++)
maxProfit[i] = Math.max(maxProfit[i], result);
}
return result;
}
public static void main(String[] args) {
Offer[] offers = {
new Offer(0, 0, 1),
new Offer(0, 2, 2),
new Offer(1, 3, 2)
};
int n = 5;
System.out.println(maximizeProfit(n, offers));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Offer {
int start, end, gold;
};
bool comp(const Offer& a, const Offer& b) {
return a.start != b.start ? a.start < b.start : a.end < b.end;
}
int maximizeProfit(int n, vector<Offer>& offers) {
sort(offers.begin(), offers.end(), comp);
vector<int> maxProfit(n, 0);
int result = 0;
for (const auto& offer: offers) {
int currentProfit = offer.gold;
if (offer.start > 0)
currentProfit += maxProfit[offer.start - 1];
result = max(result, currentProfit);
for (int i = offer.start; i <= offer.end; ++i)
maxProfit[i] = max(maxProfit[i], result);
}
return result;
}
int main() {
vector<Offer> offers = { {0, 0, 1}, {0, 2, 2}, {1, 3, 2} };
int n = 5;
cout << maximizeProfit(n, offers) << endl;
return 0;
}function maximizeProfit(n, offers) {
offers.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
const maxProfit = new Array(n).fill(0);
let result = 0;
for (let [start, end, gold] of offers) {
if (start > 0) {
gold += maxProfit[start - 1];
}
result = Math.max(result, gold);
for (let i = start; i <= end; i++) {
maxProfit[i] = Math.max(maxProfit[i], result);
}
}
return result;
}
console.log(maximizeProfit(5, [[0, 0, 1], [0, 2, 2], [1, 3, 2]]));#include <stdio.h>
#include <stdlib.h>
typedef struct {
int start;
int end;
int gold;
} Offer;
int compare(const void *a, const void *b) {
Offer *offerA = (Offer *)a;
Offer *offerB = (Offer *)b;
if (offerA->start != offerB->start)
return offerA->start - offerB->start;
return offerA->end - offerB->end;
}
int maximizeProfit(int n, Offer offers[], int offersSize) {
qsort(offers, offersSize, sizeof(Offer), compare);
int *map = calloc(n, sizeof(int));
int maxProfit = 0;
for (int i = 0; i < offersSize; i++) {
int currentProfit = offers[i].gold;
if (offers[i].start > 0)
currentProfit += map[offers[i].start - 1];
maxProfit = (maxProfit > currentProfit) ? maxProfit : currentProfit;
for (int j = offers[i].start; j <= offers[i].end; j++)
map[j] = maxProfit;
}
free(map);
return maxProfit;
}
int main() {
Offer offers[] = { {0, 0, 1}, {0, 2, 2}, {1, 3, 2} };
int n = 5;
int offersSize = sizeof(offers) / sizeof(Offer);
printf("%d\n", maximizeProfit(n, offers, offersSize));
return 0;
}using System;
public struct Offer {
public int Start, End, Gold;
public Offer(int start, int end, int gold) {
Start = start;
End = end;
Gold = gold;
}
}
public class MaximizeProfit {
public static int Maximize(int n, Offer[] offers) {
Array.Sort(offers, (a, b) => a.Start != b.Start ? a.Start - b.Start : a.End - b.End);
int[] maxProfit = new int[n];
int result = 0;
foreach (var offer in offers) {
int currentProfit = offer.Gold;
if (offer.Start > 0)
currentProfit += maxProfit[offer.Start - 1];
result = Math.Max(result, currentProfit);
for (int i = offer.Start; i <= offer.End; i++)
maxProfit[i] = Math.Max(maxProfit[i], result);
}
return result;
}
public static void Main() {
Offer[] offers = {
new Offer(0, 0, 1),
new Offer(0, 2, 2),
new Offer(1, 3, 2)
};
int n = 5;
Console.WriteLine(Maximize(n, offers));
}
}Sorting offers by their start and end points, this Python function utilizes a list to track the maximum profits achievable at each house marker. Iterating through the sorted offers allows the function to update cumulative maximum profits array with new insights, demonstrating a greedy approach but ensuring optimal results are always reflected up to that index.
Time Complexity: O(m log(m) + n) from both sorting and processing through each offer's spread.
Space Complexity: O(n), attributed to the storage for the maximum profits array.
Approach 3: Sorting + Binary Search + Dynamic Programming
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.
function maximizeTheProfit(n: number, offers: number[][]): number {
offers.sort((a, b) => a[1] - b[1]);
n = offers.length;
const f: number[] = Array(n + 1).fill(0);
const g = offers.map(x => x[1]);
const search = (x: number) => {
let l = 0;
let r = n;
while (l < r) {
const mid = (l + r) >> 1;
if (g[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let i = 1; i <= n; ++i) {
const j = search(offers[i - 1][0]);
f[i] = Math.max(f[i - 1], f[j] + offers[i - 1][2]);
}
return f[n];
}func maximizeTheProfit(n int, offers [][]int) int {
sort.Slice(offers, func(i, j int) bool { return offers[i][1] < offers[j][1] })
n = len(offers)
f := make([]int, n+1)
g := []int{}
for _, o := range offers {
g = append(g, o[1])
}
for i := 1; i <= n; i++ {
j := sort.SearchInts(g, offers[i-1][0])
f[i] = max(f[i-1], f[j]+offers[i-1][2])
}
return f[n]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sorting | Time Complexity: O(m log(m)), with m indicating the number of offers (due to sorting and binary searching). |
| Greedy Approach with Sorting and Mapping | Time Complexity: O(m log(m) + n) from both sorting and processing through each offer's spread. |
| Sorting + Binary Search + Dynamic Programming | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Maximize the Profit as the Salesman easy or hard?
The problem is rated Medium on LeetCode because it requires recognizing the weighted interval scheduling pattern. Once the DP state and sorting strategy are clear, the implementation becomes straightforward.
Maximize the Profit as the Salesman Python/Java solution
Implement the solution by sorting offers by end index and using a DP array to track maximum profit. In Python or Java, combine sorting with binary search or maintain a mapping from ending house to offers for incremental DP updates.
How to solve Maximize the Profit as the Salesman in O(n)?
A near-linear approach iterates across houses and processes offers grouped by their ending index. Using a mapping from end house to offers, dynamic programming updates the best profit at each house. The complexity becomes O(n + m log m) due to the initial sorting step.
What is the best approach for Maximize the Profit as the Salesman?
The most efficient approach models the problem as weighted interval scheduling. Sort offers by ending house, then use dynamic programming with binary search to find the latest non-overlapping offer. This yields an O(m log m) time solution and O(m) space complexity.
Is Maximize the Profit as the Salesman asked at Google/Amazon/Meta?
This problem reflects a classic weighted interval scheduling pattern commonly used in interviews at companies like Google, Amazon, and Meta. Variants involving non-overlapping intervals and profit maximization frequently appear in dynamic programming interview rounds.
What data structure is used in Maximize the Profit as the Salesman?
Key data structures include arrays for dynamic programming, sorted lists of offers, and optionally a hash map that groups offers by ending index. Binary search is often used to efficiently find the last non-overlapping interval.
What is the time complexity of Maximize the Profit as the Salesman?
The optimal solution runs in O(m log m) time, where m is the number of offers. The log factor comes from sorting the offers and performing binary search to locate the last compatible non-overlapping offer during each DP transition.