Question

2830. Maximize the Profit as the Salesman

中文文档

Description

You are given an integer n representing the number of houses on a number line, numbered from 0 to n - 1.

Additionally, you are given a 2D integer array offers where offers[i] = [starti, endi, goldi], indicating that ith buyer wants to buy all the houses from starti to endi for goldi amount of gold.

As a salesman, your goal is to maximize your earnings by strategically selecting and selling houses to buyers.

Return _the maximum amount of gold you can earn_.

Note that different buyers can't buy the same house, and some houses may remain unsold.

 

Example 1:

Input: n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
Output: 3
Explanation: There are 5 houses numbered from 0 to 4 and there are 3 purchase offers.
We sell houses in the range [0,0] to 1st buyer for 1 gold and houses in the range [1,3] to 3rd buyer for 2 golds.
It can be proven that 3 is the maximum amount of gold we can achieve.

Example 2:

Input: n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]
Output: 10
Explanation: There are 5 houses numbered from 0 to 4 and there are 3 purchase offers.
We sell houses in the range [0,2] to 2nd buyer for 10 golds.
It can be proven that 10 is the maximum amount of gold we can achieve.

 

Constraints:

• 1 <= n <= 105
• 1 <= offers.length <= 105
• offers[i].length == 3
• 0 <= starti <= endi <= n - 1
• 1 <= goldi <= 103

Solutions

Solution 1: Sorting + Binary Search + Dynamic Programming

We sort all the purchase offers by $end$ in ascending order, and then use dynamic programming to solve the problem.

Define $f[i]$ to represent the maximum amount of gold we can get from the first $i$ purchase offers. The answer is $f[n]$.

For $f[i]$, we can choose not to sell the $i$th purchase offer, in which case $f[i] = f[i - 1]$; or we can choose to sell the $i$th purchase offer, in which case $f[i] = f[j] + gold_i$, where $j$ is the largest index that satisfies $end_j \leq start_i$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of purchase offers.

class Solution:
  def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
    offers.sort(key=lambda x: x[1])
    f = [0] * (len(offers) + 1)
    g = [x[1] for x in offers]
    for i, (s, _, v) in enumerate(offers, 1):
      j = bisect_left(g, s)
      f[i] = max(f[i - 1], f[j] + v)
    return f[-1]

class Solution {
  public int maximizeTheProfit(int n, List<List<Integer>> offers) {
    offers.sort((a, b) -> a.get(1) - b.get(1));
    n = offers.size();
    int[] f = new int[n + 1];
    int[] g = new int[n];
    for (int i = 0; i < n; ++i) {
      g[i] = offers.get(i).get(1);
    }
    for (int i = 1; i <= n; ++i) {
      var o = offers.get(i - 1);
      int j = search(g, o.get(0));
      f[i] = Math.max(f[i - 1], f[j] + o.get(2));
    }
    return f[n];
  }

  private int search(int[] nums, int x) {
    int l = 0, r = nums.length;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
}

class Solution {
public:
  int maximizeTheProfit(int n, vector<vector<int>>& offers) {
    sort(offers.begin(), offers.end(), [](const vector<int>& a, const vector<int>& b) {
      return a[1] < b[1];
    });
    n = offers.size();
    vector<int> f(n + 1);
    vector<int> g;
    for (auto& o : offers) {
      g.push_back(o[1]);
    }
    for (int i = 1; i <= n; ++i) {
      auto o = offers[i - 1];
      int j = lower_bound(g.begin(), g.end(), o[0]) - g.begin();
      f[i] = max(f[i - 1], f[j] + o[2]);
    }
    return f[n];
  }
};

func maximizeTheProfit(n int, offers [][]int) int {
  sort.Slice(offers, func(i, j int) bool { return offers[i][1] < offers[j][1] })
  n = len(offers)
  f := make([]int, n+1)
  g := []int{}
  for _, o := range offers {
    g = append(g, o[1])
  }
  for i := 1; i <= n; i++ {
    j := sort.SearchInts(g, offers[i-1][0])
    f[i] = max(f[i-1], f[j]+offers[i-1][2])
  }
  return f[n]
}

function maximizeTheProfit(n: number, offers: number[][]): number {
  offers.sort((a, b) => a[1] - b[1]);
  n = offers.length;
  const f: number[] = Array(n + 1).fill(0);
  const g = offers.map(x => x[1]);
  const search = (x: number) => {
    let l = 0;
    let r = n;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (g[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };
  for (let i = 1; i <= n; ++i) {
    const j = search(offers[i - 1][0]);
    f[i] = Math.max(f[i - 1], f[j] + offers[i - 1][2]);
  }
  return f[n];
}