Maximize the Profit as the Salesman

Maximize the Profit as the Salesman

What is this problem about?

In this problem, you are a salesman looking at a row of houses. You are given an array of offers, where each offer is defined as [start_house, end_house, gold]. This means a buyer will pay you gold if you sell them the contiguous block of houses from start_house to end_house. You cannot sell the same house to two different buyers. Your goal is to maximize your total gold by choosing a non-overlapping set of offers.

Why is this asked in interviews?

This is a classic Weighted Interval Scheduling problem. It is highly favored in interviews (especially at Amazon and Google) because it requires combining Sorting, Binary Search, and Dynamic Programming. It tests if you can optimize a "pick or skip" recursive choice when the intervals have varying weights and conflicting overlaps.

Algorithmic pattern used

This problem uses 1D Dynamic Programming with Binary Search.

1. Sort the offers primarily by their end_house.
2. Maintain a dp array where dp[i] is the maximum profit you can make using a subset of the first i sorted offers.
3. For the $i$-th offer [start, end, gold], you have two choices:
   • Skip it: The profit is dp[i-1].
   • Pick it: You get gold. But since you picked it, you can't pick any previous offers that overlap with it. You must find the latest offer j whose end_house is strictly less than the current start_house. Because the offers are sorted by end times, you can find this non-overlapping offer using Binary Search. The profit is gold + dp[j].
4. dp[i] = max(skip, pick).

Example explanation

Offers: [0, 1, 5], [1, 2, 4], [2, 3, 5] (already sorted by end).

• Offer 0: [0, 1, 5]. Pick it. dp[0] = 5.
• Offer 1: [1, 2, 4].
  • Skip: dp[0] = 5.
  • Pick: Gain 4. Find non-overlapping offer before start 1. There are none (Offer 0 ends at 1, which overlaps). Gain = 4.
  • dp[1] = max(5, 4) = 5.
• Offer 2: [2, 3, 5].
  • Skip: dp[1] = 5.
  • Pick: Gain 5. Find non-overlapping offer before start 2. Binary search finds Offer 0 (ends at 1, which is $< 2$). Gain = $5 + dp[0]$ = $5 + 5 = 10$.
  • dp[2] = max(5, 10) = 10. Maximum profit is 10.

Common mistakes candidates make

A frequent mistake is sorting the offers by start_house instead of end_house. Sorting by start times makes it incredibly difficult to define the "clean boundary" needed for the DP array to look backwards reliably. Another mistake is using a linear scan $O(N)$ instead of Binary Search $O(\log N)$ to find the latest non-overlapping interval, which degrades the overall time complexity from $O(N \log N)$ to $O(N^2)$.

Interview preparation tip

The Weighted Interval Scheduling pattern is a must-know. Memorize the steps: Sort by end time -> DP array -> Binary search for the rightmost non-overlapping interval -> max(include, exclude). In many languages (like Python's bisect), you can write the binary search in a single line, making this complex DP problem very quick to implement.