Maximize the Profit as the Salesman

Medium
1490.

Maximize the Profit as the Salesman

Maximize the Profit as the Salesman is a medium coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.

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^5
  • 1 <= offers.length <= 10^5
  • offers[i].length == 3
  • 0 <= start_i <= end_i <= n - 1
  • 1 <= gold_i <= 10^3
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} offers
 * @return {number}
 */
var maximizeTheProfit = function(n, offers) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= offers.length <= 10^5
  • offers[i].length == 3
  • 0 <= start_i <= end_i <= n - 1
  • 1 <= gold_i <= 10^3

Hints for Maximize the Profit as the Salesman

  1. Hint 1

    This is weighted interval scheduling: pick non-overlapping intervals of maximum total weight.

  2. Hint 2

    Let dp[i] be the best gold using only houses 0..i-1.

  3. Hint 3

    dp[i + 1] = max(dp[i], dp[start] + gold) over every offer whose end is i.

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

  1. Group (or sort) the offers by their end house.
  2. dp[0] = 0. For e = 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).
  3. 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 houses 0..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