Skip to main content
Talentd

Maximize the Profit as the Salesman - Solution & Explanation

MediumArrayHash TableBinary SearchDynamic Programming22 min readAsked at: Amazon
Practice this problem

Problem Statement

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

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m log(m) + n), primarily due to sorting and iterating through offers.
Space Complexity: O(n) for the map array.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Sorting

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.

Greedy Approach with Sorting and Mapping

Time Complexity: O(m log(m) + n), primarily due to sorting and iterating through offers.
Space Complexity: O(n) for the map array.

Sorting + Binary Search + Dynamic Programming—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming + Sorting + Binary SearchO(m log m)O(m)Best general solution for large offer lists; classic weighted interval scheduling approach
Greedy-Style DP with Sorting and Offer MappingO(n + m log m)O(n + m)When iterating directly across houses is simpler and house count n is manageable

Video Solution

Maximize the profit as the Salesman | LeetCode Weekly 359 | DP + Binary Search • Anu Sharma • 3,944 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximize the Profit as the Salesman with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays