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

<p>Additionally, you are given a 2D integer array <code>offers</code> where <code>offers[i] = [start<sub>i</sub>, end<sub>i</sub>, gold<sub>i</sub>]</code>, indicating that <code>i<sup>th</sup></code> buyer wants to buy all the houses from <code>start<sub>i</sub></code> to <code>end<sub>i</sub></code> for <code>gold<sub>i</sub></code> amount of gold.</p>

<p>As a salesman, your goal is to <strong>maximize</strong> your earnings by strategically selecting and selling houses to buyers.</p>

<p>Return <em>the maximum amount of gold you can earn</em>.</p>

<p><strong>Note</strong> that different buyers can&#39;t buy the same house, and some houses may remain unsold.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= offers.length &lt;= 10<sup>5</sup></code></li>
	<li><code>offers[i].length == 3</code></li>
	<li><code>0 &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= n - 1</code></li>
	<li><code>1 &lt;= gold<sub>i</sub> &lt;= 10<sup>3</sup></code></li>
</ul>

'''
23

seems like an interval problem but with weights -> inteval because given an offer which is an interval, I need to know where it fits best last that doesn't overlap

Can I do this as a dp? What's the maximum amount of money I can earn if I sold up to i houses. And so at every "offer" I just need to do something like dp[offer[0]] + offer[2]

Sort by the "end" house

[1 5 x] [2 5] [3 6] -> this brings an issue because [2 5] covers 3 but i don't say it does, because I sort by end house

Ah maybe sort by the start house because I'm imagining that we can have a stack that contains the valid intervals, and then you straight up pop the ones that are overlapping...and because you sort by start time, it must be that if the current one overlaps with the previous, the next one would also overlap? Yes because you compare by end time...

What if we sort by the end house from least to greatest and then the opposite from the start if the end times are the same, so that guarentees if [5 6] has a problem then you know [4 6] will also have the same problem with the same interval but that gets into the issue of if you have [5 7] and the intervals with 4 got popped off from the last example like [4 6] but maybe you wanted to keep it

this seems to be getting complicated, the problem with the stack is that you may pop off answers that will work for the next offer for the current offer...

or maybe it's like "what is the best answer at this interval and everytime you do the popping off and stuff you update your answer and so when you get to [4 7], you just look at the dp for the interval at [3]" which may not exist so you need to do a left search...

Actually even simpler -> you go with the basic idea that if I'm at offer i, then I take what is the max I can make at offer[i][0] (start) + your current offer. I realize that you have to do a prefix max because any offer that is afterwards can use yours so if you have a dp[3] = 10, then dp[5] should be at least 10 because any offers that start at 5 can use offers that essentially end at 3

Minor optimization -> don't sort you realize you just need to go through the offers that match exactly at the ith index you're at (ith house) so just rearrange to get rid of the sort time

Time Complexity: O(n + m)
Space Complexity: O(n)
'''

class Solution:
    def maximizeTheProfit(self, n: int, offers: List[List[int]]) -> int:
        new_offers = defaultdict(list)
        
        for offer in offers:
            new_offers[offer[1]].append((offer[0], offer[2]))
            
        dp = [0] * n
        j = 0
        
        for i in range(n):
            if i > 0:
                dp[i] = dp[i - 1]
                
            for start, cost in new_offers[i]:
                dp[i] = max(dp[i], (dp[start - 1] if start > 0 else 0) + cost)
                j += 1
                   
        return dp[-1]
        
48600