#2830
Maximize the Profit as the Salesman
expert · 1030 · lc medium +32 · verified · 38.1% accepted · 717 likes · top 17%
Description
An integer n represents the number of houses on a number line, numbered 0 to n - 1. A 2D array offers is given where offers[i] = [starti, endi, goldi], meaning buyer i will pay goldi gold for all houses from starti to endi.
Maximize earnings by selecting non-overlapping offers to accept.
Return the maximum amount of gold earnable. Different buyers cannot purchase the same house; some houses may go 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.
Code
1
2
3