Problem Description

You have n houses arranged in a line, numbered from 0 to n - 1.

You receive multiple purchase offers for these houses. Each offer is represented as [start, end, gold], meaning a buyer wants to purchase all houses from position start to position end (inclusive) and is willing to pay gold amount for them.

Your task is to select which offers to accept to maximize your total earnings. The key constraint is that each house can only be sold once - if two offers overlap (share any common houses), you cannot accept both offers.

For example:

• If you have offers [0, 2, 5] and [1, 3, 6], you cannot accept both since they both include houses 1 and 2
• If you have offers [0, 1, 5] and [2, 3, 6], you can accept both since they don't share any houses

The goal is to find the maximum total gold you can earn by strategically choosing which non-overlapping offers to accept. Some houses may remain unsold if that leads to higher total earnings.

Intuition

The problem asks us to select non-overlapping intervals (house ranges) to maximize profit. This is a classic interval scheduling problem with weights.

First, let's think about how to handle overlapping offers. If we process offers in a random order, it becomes difficult to determine which previous offers conflict with the current one. However, if we sort the offers by their ending position, we gain a useful property: when considering an offer, all potentially compatible offers that end before this offer starts are already processed.

This leads us to dynamic programming. For each offer, we face a choice: take it or skip it. If we skip it, our profit remains the same as before. If we take it, we need to add its value to the best profit we could achieve from offers that don't conflict with it.

The key insight is that after sorting by end position, finding compatible offers becomes easier. For an offer starting at position s, we need to find all previous offers that end before s. Since offers are sorted by end position, we can use binary search to efficiently find the rightmost offer that ends before position s.

Let's define f[i] as the maximum profit from considering the first i offers. For each offer i:

• If we don't take it: f[i] = f[i-1]
• If we take it: f[i] = f[j] + gold_i, where j is the index of the last offer that doesn't conflict

The answer is the maximum of these two choices. By processing offers in sorted order and using binary search to find compatible offers, we can solve this efficiently in O(n log n) time.

Learn more about Binary Search, Dynamic Programming and Sorting patterns.

Solution Approach

Let's implement the solution step by step based on our intuition:

Step 1: Sort the offers

offers.sort(key=lambda x: x[1])

We sort all offers by their ending position in ascending order. This allows us to efficiently find compatible offers later.

Step 2: Initialize dynamic programming array

f = [0] * (len(offers) + 1)

Create an array f where f[i] represents the maximum gold we can earn from the first i offers. We use size len(offers) + 1 to handle the base case where we consider 0 offers.

Step 3: Extract ending positions for binary search

g = [x[1] for x in offers]

Create an array g containing just the ending positions of all offers. Since offers are sorted by ending position, g is also sorted, making it suitable for binary search.

Step 4: Process each offer

for i, (s, _, v) in enumerate(offers, 1):
    j = bisect_left(g, s)
    f[i] = max(f[i - 1], f[j] + v)

For each offer at index i (1-indexed in the DP array):

• Extract the start position s and gold value v
• Use bisect_left(g, s) to find the index j of the rightmost offer that ends before position s. This gives us the last non-conflicting offer
• Calculate f[i] as the maximum of:
  • f[i - 1]: Don't take the current offer
  • f[j] + v: Take the current offer and add its value to the best result from non-conflicting offers

Step 5: Return the result

return f[-1]

The last element of f contains the maximum gold we can earn from all offers.

Time Complexity: O(n log n) for sorting and O(n log n) for n binary searches, giving overall O(n log n)

Space Complexity: O(n) for the DP array and the array of ending positions

Example Walkthrough

Let's walk through a concrete example with 4 houses (numbered 0-3) and the following offers:

• Offer 1: [0, 2, 5] - Buy houses 0, 1, 2 for 5 gold
• Offer 2: [1, 3, 6] - Buy houses 1, 2, 3 for 6 gold
• Offer 3: [0, 1, 3] - Buy houses 0, 1 for 3 gold

Step 1: Sort offers by ending position After sorting by the second element (end position):

• Offer 3: [0, 1, 3] (ends at 1)
• Offer 1: [0, 2, 5] (ends at 2)
• Offer 2: [1, 3, 6] (ends at 3)

Step 2: Initialize DP array f = [0, 0, 0, 0] where f[i] represents max profit from first i offers

Step 3: Extract ending positions g = [1, 2, 3] (ending positions of sorted offers)

Step 4: Process each offer

Processing Offer 3 [0, 1, 3]:

• Start position s = 0
• bisect_left(g, 0) returns 0 (no offers end before position 0)
• f[1] = max(f[0], f[0] + 3) = max(0, 0 + 3) = 3
• DP array: [0, 3, 0, 0]

Processing Offer 1 [0, 2, 5]:

• Start position s = 0
• bisect_left(g, 0) returns 0 (no offers end before position 0)
• f[2] = max(f[1], f[0] + 5) = max(3, 0 + 5) = 5
• DP array: [0, 3, 5, 0]

Processing Offer 2 [1, 3, 6]:

• Start position s = 1
• bisect_left(g, 1) returns 0 (no offers end strictly before position 1)
• f[3] = max(f[2], f[0] + 6) = max(5, 0 + 6) = 6
• DP array: [0, 3, 5, 6]

Step 5: Return result The maximum gold we can earn is f[3] = 6 by accepting Offer 2 [1, 3, 6].

Note: We cannot accept both Offer 1 and Offer 2 because they overlap at houses 1 and 2. The algorithm correctly identifies that taking Offer 2 alone (6 gold) is better than taking Offer 3 alone (3 gold) or Offer 1 alone (5 gold).

Solution Implementation

Time and Space Complexity

The time complexity is O(m × log m), where m is the number of offers (length of the offers list).

• Sorting the offers takes O(m × log m) time
• Creating list g with list comprehension takes O(m) time
• The for loop runs m iterations, and within each iteration:
  • bisect_left(g, s) performs binary search which takes O(log m) time
  • The max operation takes O(1) time
• Total for the loop: O(m × log m)
• Overall: O(m × log m) + O(m) + O(m × log m) = O(m × log m)

The space complexity is O(m), where m is the number of offers.

• List f has size m + 1, which is O(m)
• List g has size m, which is O(m)
• The sorting operation may use O(m) additional space depending on the implementation
• Overall: O(m) + O(m) = O(m)

Note: The reference answer uses n to denote the number of purchase offers, while in the code, n is actually a different parameter (likely representing the number of houses), and the number of offers is len(offers). The complexity analysis is based on the number of offers, which I've denoted as m for clarity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Non-Overlapping Check

The Problem: A common mistake is using bisect_left(end_positions, start) to find non-overlapping offers. This finds offers where end < start, but overlapping occurs when offers share ANY house. Two offers [s1, e1] and [s2, e2] overlap if they share any position, meaning they DON'T overlap only when e1 < s2 OR e2 < s1.

Why This Works (but is subtle): The code actually works correctly because:

• We sort by end position
• bisect_left(end_positions, start) finds the leftmost position where we could insert start
• This gives us the index of the last offer with end < start
• Since offers are sorted by end position, all offers before this index have end < start, making them non-overlapping

The Confusion: Many developers mistakenly think they need end <= start for non-overlap, leading them to use bisect_right instead. This would be incorrect because offers [0, 2] and [3, 5] don't overlap (house 2 and house 3 are different), but using bisect_right would incorrectly exclude valid combinations.

Pitfall 2: Off-by-One Error in DP Indexing

The Problem: The code uses 1-based indexing for the DP array (enumerate(offers, 1)), which can be confusing. Developers might accidentally mix 0-based and 1-based indexing, especially when accessing offers[i] vs dp[i].

Solution: Be consistent with indexing. Here's an alternative 0-based approach:

dp = [0] * len(offers)
for i in range(len(offers)):
    start, end, profit = offers[i]
    j = bisect_left(end_positions, start)
  
    # Take current offer
    take = profit + (dp[j-1] if j > 0 else 0)
  
    # Skip current offer
    skip = dp[i-1] if i > 0 else 0
  
    dp[i] = max(take, skip)

return dp[-1] if offers else 0

Pitfall 3: Edge Case - Empty Offers List

The Problem: If the offers list is empty, dp[-1] will access an empty list, causing an IndexError.

Solution: Add a guard clause:

if not offers:
    return 0

Pitfall 4: Misunderstanding Binary Search Return Value

The Problem: bisect_left returns an insertion point, not necessarily an existing index. If no offer ends before the current start, it returns 0, which correctly maps to dp[0] = 0 (no previous offers taken).

Key Insight: The beauty of this solution is that dp[0] = 0 serves as a sentinel value, representing "no offers taken yet," which naturally handles the case when the current offer doesn't conflict with any previous offers.