2830. Maximize the Profit as the Salesman

MediumArrayBinary SearchDynamic ProgrammingSorting

Problem Description

In this problem, you have an area consisting of a number of houses in a row, specifically n houses, indexed from 0 to n - 1. There's an opportunity to sell these houses to various buyers. Buyers come with various offers, and each buyer is represented by three components in an array: the start index, the end index, and the gold they are willing to pay. The start and end indices indicate the range of houses that the buyer is interested in purchasing, inclusive. The goal is to maximize the amount of gold you earn by selling these houses to the buyers.

However, there are two constraints to consider:

A house can only be sold to one buyer.
Some houses may not be sold at all if that maximizes the total earnings.

You need to formulate a strategy that selects which offers to accept to maximize your profit and return the maximum amount of gold you can earn.

Intuition

The intuition behind the solution involves solving the problem using dynamic programming. We're looking to maximize earnings, but we also need to ensure that the same house isn't sold to different buyers. This problem appears similar to the "Weighted Interval Scheduling" problem, where we aim to find the maximum weight (in this case, gold) of non-overlapping intervals (here, the house ranges).

Here is the general approach to arrive at the solution:

Sort all the offers by their end index. This allows us to process the offers in order and use a greedy approach to consider the latest offers without looking back to previous offers that end later.
Initialize an array f to keep track of the maximum gold that can be accumulated by considering offers up to the current index. This is the dynamic programming table, where f[i] represents the maximum earnings by considering offers up to the i-th offer.
Iterate over the sorted offers, and for each offer, find the previous non-conflicting offer's index j using binary search (bisect_left in Python), which will give the index of the rightmost offer that doesn't overlap with the current one.
Update the dynamic programming table f for the current offer index i by making a decision: either take the current offer added to the best we could do up to offer j, or stick with the best earnings up to the previous offer i-1. This is expressed as:
```
f[i] = max(f[i - 1], f[j] + v)
```
Here, v is the amount of gold of the current offer. This decision ensures we either extend our current earnings with the current offer, if it's beneficial, or we do not sell to the current buyer if it doesn't increase our earnings.
The maximum gold earned is then the last value in the f array after considering all offers.

By sorting the offers, using dynamic programming to store intermediate results, and binary search to find non-overlapping intervals efficiently, we are able to find the solution in a time-complex manner, which significantly reduces the time complexity compared to a naive approach that might check every possible combination of sales.

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

Solution Approach

To solve this problem using the described intuition, let’s walk through the implementation details step by step:

Sorting Offers: The first step involves sorting the offers array based on the end index of each offer. We do this because once we've processed an offer, we don't have to go back and consider earlier offers that may overlap with newer offers. We use the sort() method of a list in Python with a lambda function as the key to sort the offers by their end index.
```
offers.sort(key=lambda x: x[1])
```
Dynamic Programming Table Initialization: We initialize a dynamic programming table f with a length of len(offers) + 1. The first element is implicitly 0, as no gold can be earned without accepting any offers. We also create a list g which contains just the end indices of the sorted offers for quicker access during binary search.
```
f = [0] * (len(offers) + 1)
g = [x[1] for x in offers]
```
Iterating Through Offers: We iterate through the offers using an enumerate function starting from 1, since our dynamic programming table starts from index 1. This iteration gives us each offer's start index, end index, and gold alongside the iteration index i.
```
for i, (s, _, v) in enumerate(offers, 1):
```
Binary Search for Non-Conflicting Offers: Within the loop, for each offer, we use the bisect_left function to perform a binary search on list g. We're looking for the rightmost offer that does not conflict with the current offer based on its starting index. This efficiently finds us the index j for the previous offer that doesn't overlap with the current one.
```
j = bisect_left(g, s)
```
Dynamic Programming Decision: The core of the solution is the dynamic programming decision made in each iteration. For each offer, we decide if adding its value to the best value we could obtain before it (cumulative profit up to offer j) is better than the maximum gold we can achieve without it (f[i - 1]).
```
f[i] = max(f[i - 1], f[j] + v)
```
Returning the Final Result: After the loop, the last element in the f list represents the maximum gold we can earn by selling the houses according to the problem constraints. This value is returned as the final result.
```
return f[-1]
```

In terms of algorithms and patterns, the solution involves a dynamic programming approach to track and maximize profits, a greedy approach to prioritize processing later offers, and a binary search for efficiently finding compatible offers. Data structures used include lists (arrays in some other languages) for sorting offers and keeping track of dynamic states in the decision process.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example to illustrate the solution approach. Assume we have the following offers for 4 houses indexed from 0 to 3:

offers = [[0, 1, 10], [0, 2, 15], [2, 3, 10], [1, 3, 20]]

Here's how we would walk through the solution:

Sorting Offers: We sort the offers array by the end index:

offers after sorting = [[0, 1, 10], [0, 2, 15], [1, 3, 20], [2, 3, 10]]

Dynamic Programming Table Initialization: We initialize our dynamic programming table f with zeroes and an additional element for the base case, f = [0, 0, 0, 0, 0]. We also create a list g of end indices [1, 2, 3, 3].
Iterating Through Offers: We start iterating through the sorted offers:
- For the first offer [0, 1, 10], there are no previous non-conflicting offers, so f[1] = max(f[0], 0 + 10) = 10.
- For the second offer [0, 2, 15], similarly, there are no previous non-conflicting offers, so f[2] = max(f[1], 0 + 15) = 15 (since 15 is greater than 10).
- For the third offer [1, 3, 20], we use binary search to find the index of non-conflicting offer. The search returns 2, which means the first offer is not conflicting. So, f[3] = max(f[2], f[1] + 20) = max(15, 10 + 20) = 30.
- For the fourth offer [2, 3, 10], the search returns the same index since the previous offer is overlapping, we cannot add the current offer to it. So, f[4] = max(f[3], f[2] + 10) = max(30, 15 + 10) = 30.
Returning the Final Result: After iterating through all offers, the last value in f is 30, which is the maximum gold we can earn.

This walkthrough shows how dynamic programming is used to keep track of maximum earnings at each step by either taking the new offer or sticking with the previous best option. The binary search is key to quickly finding the best prior non-conflicting offer that we can use as a base for adding the new offer's gold.

Solution Implementation

1from bisect import bisect_left
2from typing import List
3
4class Solution:
5    def maximize_the_profit(self, n: int, offers: List[List[int]]) -> int:
6        # Sort the offers based on their ending times
7        offers.sort(key=lambda offer: offer[1])
8      
9        # Initialize an array to store the maximum profit
10        # that can be obtained up to each offer index
11        maximum_profits = [0] * (len(offers) + 1)
12      
13        # Extract the ending times to facilitate binary search later
14        ending_times = [offer[1] for offer in offers]
15      
16        # Iterate through each offer
17        for i, (start_time, end_time, value) in enumerate(offers, 1):
18            # Find the index of the latest offer that ends before the current offer starts
19            index = bisect_left(ending_times, start_time)
20          
21            # Update the maximum profit for the current position
22            # It's either we take the current offer and add its value to the profit
23            # at the aforementioned index, or we ignore the current offer and carry
24            # forward the previous maximum profit
25            maximum_profits[i] = max(maximum_profits[i - 1], maximum_profits[index] + value)
26      
27        # Return the maximum profit at the end of the array,
28        # which is the profit after considering all offers
29        return maximum_profits[-1]
30

1class Solution {
2  
3    // Method that aims to maximize the profit based on the offers list and return the maximum profit.
4    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
5        // Sort the offers based on their end times.
6        offers.sort((a, b) -> a.get(1) - b.get(1));
7
8        // Initialize a dynamic programming array to store the maximum profit up to each offer.
9        int[] maxProfitUpTo = new int[offers.size() + 1];
10      
11        // Create an array to store the end times of each offer.
12        int[] endTimes = new int[offers.size()];
13        for (int i = 0; i < offers.size(); ++i) {
14            endTimes[i] = offers.get(i).get(1);
15        }
16      
17        // Calculate the maximum profit for each offer.
18        for (int i = 1; i <= offers.size(); ++i) {
19            var currentOffer = offers.get(i - 1);
20          
21            // Find the latest offer that does not conflict with the current offer.
22            int latestNonConflictingIndex = binarySearch(endTimes, currentOffer.get(0));
23          
24            // Update the maximum profit for the current offer, considering not taking or taking the current offer.
25            maxProfitUpTo[i] = Math.max(maxProfitUpTo[i - 1], maxProfitUpTo[latestNonConflictingIndex] + currentOffer.get(2));
26        }
27      
28        // Return the maximum profit after considering all offers.
29        return maxProfitUpTo[offers.size()];
30    }
31
32    // Binary search method to find the maximum index of offers that end before the given start time x.
33    private int binarySearch(int[] times, int startTime) {
34        int left = 0, right = times.length;
35        while (left < right) {
36            int mid = (left + right) >> 1; // Equivalent to dividing by 2.
37            if (times[mid] >= startTime) {
38                right = mid;
39            } else {
40                left = mid + 1;
41            }
42        }
43        return left;
44    }
45}
46

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Function to maximize the profit based on the given offers
7    int maximizeTheProfit(int totalOffers, std::vector<std::vector<int>>& offers) {
8        // Sort the offers based on the ending time
9        std::sort(offers.begin(), offers.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
10            // If a finishes before b, then a should come before b
11            return a[1] < b[1];
12        });
13      
14        // Update the totalOffers to the size of the offers vector
15        totalOffers = offers.size();
16      
17        // Dynamic programming array to store the maximum profit at each step
18        std::vector<int> maxProfit(totalOffers + 1, 0);
19      
20        // Vector to store the end times of the offers
21        std::vector<int> endTimes;
22        for (auto& offer : offers) {
23            // Add the end time of each offer to the endTimes vector
24            endTimes.push_back(offer[1]);
25        }
26      
27        // Loop through each offer to calculate the maximum profit
28        for (int i = 1; i <= totalOffers; ++i) {
29            // Current offer details: start time, end time, and profit
30            auto currentOffer = offers[i - 1];
31            // Find the last offer that finishes before the current one starts
32            int prevAvailable = std::lower_bound(endTimes.begin(), endTimes.end(), currentOffer[0]) - endTimes.begin();
33            // Update the maxProfit at i considering the current offer
34            maxProfit[i] = std::max(maxProfit[i - 1], maxProfit[prevAvailable] + currentOffer[2]);
35        }
36      
37        // The last element of maxProfit contains the maximum profit possible
38        return maxProfit[totalOffers];
39    }
40};
41

1function maximizeTheProfit(totalOffers: number, priceOffers: number[][]): number {
2    // Sort the offers by the second element of each offer tuple, which is the sell time.
3    priceOffers.sort((offerA, offerB) => offerA[1] - offerB[1]);
4
5    // The total number of offers is updated to the length of the provided offer list.
6    totalOffers = priceOffers.length;
7
8    // Initialize an array for dynamic programming to store the maximum profit till each offer.
9    const maxProfitAtIndex: number[] = Array(totalOffers + 1).fill(0);
10
11    // An array to store the sell time of each offer. This is used for binary search.
12    const sellTimes = priceOffers.map(offer => offer[1]);
13
14    // Helper function to perform binary search for the index of the first sell time that is >= x.
15    const findSellTimeIndex = (targetTime: number): number => {
16        let left = 0;
17        let right = totalOffers;
18        while (left < right) {
19            const mid = (left + right) >> 1; // Same as Math.floor((left + right) / 2)
20            if (sellTimes[mid] >= targetTime) {
21                right = mid;
22            } else {
23                left = mid + 1;
24            }
25        }
26        return left;
27    };
28
29    // Calculate the maximum profit for each offer using dynamic programming.
30    for (let i = 1; i <= totalOffers; ++i) {
31        // Using binary search to find the latest offer which sell time is less than or equal to the current offer's buy time.
32        const latestCompatibleOfferIndex = findSellTimeIndex(priceOffers[i - 1][0]);
33
34        // Update the maximum profit at this index by comparing:
35        // - The maximum profit till the previous offer, and
36        // - The maximum profit till the latest compatible offer plus the current offer's profit.
37        maxProfitAtIndex[i] = Math.max(maxProfitAtIndex[i - 1], maxProfitAtIndex[latestCompatibleOfferIndex] + priceOffers[i - 1][2]);
38    }
39
40    // The last element in maxProfitAtIndex contains the maximum profit that can be achieved.
41    return maxProfitAtIndex[totalOffers];
42}
43

Time and Space Complexity

Time Complexity

The given code has several different operations, each with its own time complexity, which we should analyze step by step:

Sorting the offers: offers.sort(key=lambda x: x[1]) sorts the list based on the second element of the sublists. The sorting algorithm used by Python's sort() function is Timsort, which has a time complexity of O(n log n), where n is the length of the list to sort. Since all offers are being sorted, this step has a time complexity of O(n log n).
Preparing a list for dynamic programming: f = [0] * (len(offers) + 1) initializes a list with len(offers) + 1 elements, each being 0. This has a time complexity of O(m), where m is the length of the offers list plus one. However, this is overshadowed by the sorting step, as list initialization is linear O(m) and m would be equal to n for the purpose of comparison.
Creating another list for binary search: g = [x[1] for x in offers] creates a list of end times for binary search. This step has a time complexity of O(n) as it involves going through each of the n offers.
Iterating over the offers and applying dynamic programming with a binary search: The loop for i, (s, _, v) in enumerate(offers, 1): iterates n times. Inside this loop, j = bisect_left(g, s) performs a binary search which has a logarithmic time complexity, O(log n), and the dynamic programming state update f[i] = max(f[i - 1], f[j] + v) is performed in O(1) time. Hence, the nested operation's time complexity is O(n log n) because the binary search is called per iteration over the n elements.

Total time complexity is dominated by the sorting and the loop with binary search, both O(n log n), so the overall time complexity is O(n log n).

Space Complexity

The space complexity is determined by the space used to store data structures in the algorithm:

The sorted offers list does not require additional space as it is sorted in-place.
The dynamic programming list f of size len(offers) + 1 adds O(n) space complexity.
The list g, used for binary search which retains the end times of offers, also adds another O(n) space complexity.
The stack space used in sorting and binary search is O(log n), due to the recursive nature of these algorithms (assuming the worst-case scenario), but this is generally considered a lesser term compared to the previous space allocations.

Total space complexity is the sum of the space used, which is O(n) with respect to the number of offers (n being the length of the offers list).

In conclusion, the overall time complexity is O(n log n) and space complexity is O(n).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: