#2830

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximize the Profit as the Salesman

Determine the maximum profit a salesman can earn by strategically selecting non-overlapping offers on consecutive houses.

array hash table binary search dynamic programming sorting

Problem Statement

You are given an integer n representing houses numbered from 0 to n - 1 along a number line. Each house can be sold at most once, and buyers submit purchase offers that include a start index, an end index, and the gold amount they are willing to pay.

Given a 2D integer array offers where offers[i] = [starti, endi, goldi], determine the maximum total gold you can earn by accepting a subset of offers without overlapping house ranges. Optimize the selection of offers to ensure the sum of gold is maximized.

Examples

Example 1

Input: n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]

Output: 3

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

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

Solution Approach

Sort Offers by End Index

First, sort all offers based on their end index. This ordering allows sequential scanning and ensures that when evaluating an offer, all potential previous compatible offers have already been considered.

Dynamic Programming with Hash Lookup

Maintain a DP array where dp[i] represents the maximum gold obtainable up to house i. Use a hash table to map end indices to DP values, enabling constant-time lookups of compatible previous offers to avoid overlapping selections.

Iterate and Update Maximum Profit

Scan through sorted offers, for each offer check the best profit achievable including this offer using the DP hash. Update the DP array or map with the new maximum if including this offer increases total gold, ensuring non-overlapping constraints are maintained.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is dominated by sorting offers O(m log m) where m is the number of offers, plus linear DP iteration O(m), yielding O(m log m) total. Space complexity is O(n) for the DP array or O(m) if using a hash map to store intermediate maximum profits.

What Interviewers Usually Probe

Watch for overlapping ranges; naive selection leads to suboptimal profit.
Consider how dynamic programming can combine prior optimal selections efficiently.
Using a hash map for end indices can significantly reduce lookup time.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort offers by end index before DP calculation.
Including overlapping offers that invalidate prior selections.
Ignoring hash table optimizations, leading to slower O(n*m) checks.

Follow-up variants

Allow offers with partial overlaps and maximize profit using interval scheduling with weights.
Restrict gold amounts to multiples of a constant and compute maximum using modular arithmetic DP.
Add a cost for skipping houses and maximize net profit including both sales and skip penalties.

FAQ

What is the main strategy to maximize profit in Maximize the Profit as the Salesman?

Use array scanning combined with dynamic programming and hash lookups to select non-overlapping offers with the highest cumulative gold.

Why do we need to sort offers by end index?

Sorting ensures when considering an offer, all prior compatible offers are already evaluated, simplifying dynamic programming updates.

Can overlapping offers ever be selected?

No, overlapping offers violate the house sale constraints, and including them would reduce the total achievable gold.

How does the hash table help in the DP solution?

It maps end indices to maximum profits, allowing constant-time lookups of compatible previous offers, improving efficiency over linear searches.

What common mistakes should I avoid in this problem?

Do not forget to sort offers, avoid selecting overlapping offers, and ensure DP updates consider the best prior profits for non-overlapping sequences.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        offers.sort(key=lambda x: x[1])
        f = [0] * (len(offers) + 1)
        g = [x[1] for x in offers]
        for i, (s, _, v) in enumerate(offers, 1):
            j = bisect_left(g, s)
            f[i] = max(f[i - 1], f[j] + v)
        return f[-1]

Continue Practicing

#2713 maximum strictly increasing cells in a matrix #2501 longest square streak in an array #3186 maximum total damage with spell casting