LeetCode Problem 2830

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Dynamic Programming, Sorting

Solution

LeetCode 2830 - Maximize the Profit as the Salesman

Problem Understanding

This problem gives us n houses arranged on a number line and a collection of purchase offers. Each offer is represented as [start, end, gold], meaning a buyer wants to purchase every house in the inclusive range [start, end] and is willing to pay gold units of gold.

The key restriction is that no house can be sold more than once. Therefore, if we accept one offer covering a particular house, we cannot accept any other offer that overlaps with that house.

Our goal is to choose a subset of non-overlapping offers whose total gold value is as large as possible.

The input consists of:

• n, the number of houses, indexed from 0 to n - 1
• offers, a list of purchase proposals

The output is a single integer representing the maximum amount of gold that can be earned.

The constraints are important:

• Up to 100,000 houses
• Up to 100,000 offers

These limits immediately rule out exponential or quadratic solutions. We need something close to O(m log m) or O(n + m), where m is the number of offers.

This problem is fundamentally about selecting a maximum-profit set of non-overlapping intervals. Each offer corresponds to an interval on the number line, and overlapping intervals cannot both be chosen.

Important edge cases include:

• Multiple offers covering exactly the same range.
• A single very profitable offer versus many smaller offers.
• Offers that touch but do not overlap, such as [0,1] and [2,3], which are allowed simultaneously.
• Houses that are never sold.
• The minimum input size with only one house and one offer.
• Large numbers of offers ending at the same position.

Approaches

Brute Force

A brute-force solution would consider every possible subset of offers.

For each subset, we would verify whether any two selected offers overlap. If the subset is valid, we would compute its total profit and keep track of the maximum.

This approach is correct because every possible selection is examined, guaranteeing that the optimal answer is found.

Unfortunately, with up to 100,000 offers, there are 2^m possible subsets. Even for a few dozen offers this becomes impossible, making the approach completely infeasible.

Key Insight

The problem is a variant of weighted interval scheduling.

Each offer is an interval:

• Start position
• End position
• Profit (gold)

We need the maximum total profit from a set of non-overlapping intervals.

Instead of thinking about subsets of offers, we process houses from left to right and maintain dynamic programming information.

Define:

dp[i] = maximum profit obtainable using houses in the range [0, i - 1]

When considering house position i, there are two possibilities:

1. Do not end any accepted offer at house i.
2. Accept an offer ending at house i.

If an offer is [start, end, gold] and end = i, then before taking this offer we may freely use houses before start.

Therefore:

candidate = dp[start] + gold

We take the maximum among all such possibilities.

By grouping offers according to their ending house, we can process everything efficiently in linear time after grouping.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^m · m)	O(m)	Enumerates all subsets of offers
Optimal Dynamic Programming	O(n + m)	O(n + m)	Processes houses left to right and evaluates offers ending at each position

Where m = len(offers).

Algorithm Walkthrough

1. Create a list of offers ending at each house.

For every offer [start, end, gold], store (start, gold) inside a bucket corresponding to end. 2. Create a DP array of length n + 1.

Let dp[i] represent the maximum profit obtainable using only houses before index i. 3. Iterate through house positions from 0 to n - 1.

First carry forward the previous best profit:

dp[i + 1] = dp[i]

This represents skipping all offers that end at house i. 4. Process every offer ending at house i.

Suppose the offer is (start, gold).

If we accept this offer, then all houses in [start, i] become occupied by that offer.

The best profit achievable before that interval begins is dp[start].

Therefore the total profit becomes:

dp[start] + gold 5. Update:

dp[i + 1] = max(dp[i + 1], dp[start] + gold) 6. Continue until all houses have been processed. 7. Return dp[n].

This represents the best profit obtainable using all houses.

Why it works

The DP invariant is:

dp[i] always stores the maximum profit obtainable using only houses strictly before position i.

When processing house i, every valid solution either ignores offers ending at i or chooses exactly one offer ending at i. If an offer [start, i] is chosen, all earlier decisions must lie completely before start, whose optimal profit is already stored in dp[start].

Since every possibility is considered exactly once and every state uses previously computed optimal states, the resulting answer is optimal.

Python Solution

from typing import List

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        ending_offers = [[] for _ in range(n)]

        for start, end, gold in offers:
            ending_offers[end].append((start, gold))

        dp = [0] * (n + 1)

        for end in range(n):
            dp[end + 1] = dp[end]

            for start, gold in ending_offers[end]:
                dp[end + 1] = max(
                    dp[end + 1],
                    dp[start] + gold
                )

        return dp[n]

The implementation begins by grouping offers according to their ending position. This allows us to efficiently access all offers that become relevant when processing a particular house.

The dp array stores the optimal profit up to each point on the number line. The transition dp[end + 1] = dp[end] represents skipping offers ending at the current house.

For every offer ending at the current position, we compute the profit obtained by taking that offer. Since the interval starts at start, the best compatible profit is exactly dp[start]. Adding the offer's gold value gives the profit for selecting that offer.

The maximum among all possibilities becomes the DP value for the next position.

Finally, dp[n] contains the optimal profit across all houses.

Go Solution

func maximizeTheProfit(n int, offers [][]int) int {
	endingOffers := make([][][2]int, n)

	for _, offer := range offers {
		start := offer[0]
		end := offer[1]
		gold := offer[2]

		endingOffers[end] = append(
			endingOffers[end],
			[2]int{start, gold},
		)
	}

	dp := make([]int, n+1)

	for end := 0; end < n; end++ {
		dp[end+1] = dp[end]

		for _, offer := range endingOffers[end] {
			start := offer[0]
			gold := offer[1]

			candidate := dp[start] + gold
			if candidate > dp[end+1] {
				dp[end+1] = candidate
			}
		}
	}

	return dp[n]
}

Go-specific Notes

The Go implementation follows the same logic as the Python version.

Since Go does not have tuples, each stored offer is represented using a fixed-size array [2]int containing (start, gold).

All values fit comfortably inside Go's int type because the maximum possible profit is at most:

100000 × 1000 = 100,000,000

which is well within the range of a 32-bit signed integer.

Worked Examples

Example 1

Input

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

Grouped by ending position:

End	Offers
0	(0,1)
1	none
2	(0,2)
3	(1,2)
4	none

Initial:

i	dp
Start	[0,0,0,0,0,0]

Process end = 0:

• Carry forward: dp[1] = 0

• Offer (0,1):

• dp[0] + 1 = 1

dp
[0,1,0,0,0,0]

Process end = 1:

• Carry forward: dp[2] = 1

dp
[0,1,1,0,0,0]

Process end = 2:

• Carry forward: dp[3] = 1

• Offer (0,2)

• dp[0] + 2 = 2

dp
[0,1,1,2,0,0]

Process end = 3:

• Carry forward: dp[4] = 2

• Offer (1,2)

• dp[1] + 2 = 3

dp
[0,1,1,2,3,0]

Process end = 4:

• Carry forward: dp[5] = 3

dp
[0,1,1,2,3,3]

Answer:

3

Example 2

Input

n = 5
offers = [[0,0,1],[0,2,10],[1,3,2]]

Grouped offers:

End	Offers
0	(0,1)
2	(0,10)
3	(1,2)

Processing:

End	DP State
Initial	[0,0,0,0,0,0]
0	[0,1,0,0,0,0]
1	[0,1,1,0,0,0]
2	[0,1,1,10,0,0]
3	[0,1,1,10,10,0]
4	[0,1,1,10,10,10]

Answer:

10

The large offer [0,2] dominates every other valid combination.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each house and each offer is processed exactly once
Space	O(n + m)	DP array plus grouped offers

Here, m denotes the number of offers. Building the buckets requires O(m) work. The DP loop visits each house once, and every offer is examined exactly once during the processing of its ending position. Therefore the total running time is linear in the size of the input.

Test Cases

from typing import List

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        ending_offers = [[] for _ in range(n)]

        for start, end, gold in offers:
            ending_offers[end].append((start, gold))

        dp = [0] * (n + 1)

        for end in range(n):
            dp[end + 1] = dp[end]

            for start, gold in ending_offers[end]:
                dp[end + 1] = max(dp[end + 1], dp[start] + gold)

        return dp[n]

s = Solution()

assert s.maximizeTheProfit(5, [[0,0,1],[0,2,2],[1,3,2]]) == 3  # example 1

assert s.maximizeTheProfit(5, [[0,0,1],[0,2,10],[1,3,2]]) == 10  # example 2

assert s.maximizeTheProfit(1, [[0,0,5]]) == 5  # single house

assert s.maximizeTheProfit(3, [[0,0,2],[1,1,3],[2,2,4]]) == 9  # all disjoint

assert s.maximizeTheProfit(4, [[0,3,5],[0,3,10]]) == 10  # identical ranges

assert s.maximizeTheProfit(5, [[0,1,4],[2,4,7]]) == 11  # touching intervals

assert s.maximizeTheProfit(5, [[0,4,10],[0,1,4],[2,4,8]]) == 12  # split beats large interval

assert s.maximizeTheProfit(6, [[0,2,5],[1,3,100],[4,5,6]]) == 106  # profitable overlap choice

assert s.maximizeTheProfit(5, [[0,0,1],[0,0,5],[0,0,3]]) == 5  # choose best duplicate offer

assert s.maximizeTheProfit(
    7,
    [[0,1,5],[2,3,6],[4,5,7],[0,5,15]]
) == 18  # many small intervals beat one large interval

Test Summary

Test	Why
Example 1	Verifies standard overlapping intervals
Example 2	Verifies choosing one large profitable interval
Single house	Minimum input size
All disjoint intervals	Every offer can be accepted
Identical ranges	Must choose highest profit offer
Touching intervals	Confirms non-overlapping adjacent intervals work
Split beats large interval	Multiple offers outperform one larger offer
Profitable overlap choice	Tests optimal selection among conflicting offers
Duplicate offers	Ensures maximum profit is chosen
Many small intervals	Validates combining several compatible offers

Edge Cases

Multiple Offers Covering the Same Range

Several buyers may offer different amounts for exactly the same interval. A buggy implementation might accidentally count more than one of them or fail to choose the most profitable one.

This solution evaluates every offer independently and updates the DP state with the maximum profit. Therefore only the best contribution survives.

Large Offer Versus Many Smaller Offers

A common mistake is to greedily choose the largest single offer. Consider an interval worth 10 gold versus two compatible intervals worth 6 and 7 gold. The correct answer is 13, not 10.

Because the DP explores both taking and skipping every interval, it naturally compares these possibilities and selects the globally optimal profit.

Offers Ending at the Same House

Many offers can share the same ending position. A solution that stores only one offer per ending house would lose information and produce incorrect answers.

The implementation stores a list of all offers ending at each house and evaluates every one of them, guaranteeing that no valid choice is overlooked.

Unsold Houses

The optimal strategy may leave some houses unsold. For example, a house might not belong to any profitable interval.

The DP state does not require every house to be sold. The carry-forward transition dp[i + 1] = dp[i] naturally handles gaps and allows houses to remain unused when that leads to a better overall profit.