<p>We have <code>n</code> jobs, where every job is scheduled to be done from <code>startTime[i]</code> to <code>endTime[i]</code>, obtaining a profit of <code>profit[i]</code>.</p>

<p>You&#39;re given the <code>startTime</code>, <code>endTime</code> and <code>profit</code> arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.</p>

<p>If you choose a job that ends at time <code>X</code> you will be able to start another job that starts at time <code>X</code>.</p>

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

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample1_1584.png" style="width: 380px; height: 154px;" /></strong></p>

<pre>
<strong>Input:</strong> startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
<strong>Output:</strong> 120
<strong>Explanation:</strong> The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.
</pre>

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

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample22_1584.png" style="width: 600px; height: 112px;" /> </strong></p>

<pre>
<strong>Input:</strong> startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
<strong>Output:</strong> 150
<strong>Explanation:</strong> The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.
</pre>

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

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2019/10/10/sample3_1584.png" style="width: 400px; height: 112px;" /></strong></p>

<pre>
<strong>Input:</strong> startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
<strong>Output:</strong> 6
</pre>

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

<ul>
	<li><code>1 &lt;= startTime.length == endTime.length == profit.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= startTime[i] &lt; endTime[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>1 &lt;= profit[i] &lt;= 10<sup>4</sup></code></li>
</ul>

from functools import lru_cache
class Solution:
    def jobScheduling(self, start: List[int], end: List[int], profit: List[int]) -> int:

        temp = zip(start, end, profit)
        temp = sorted(temp, key = lambda a: a[0])
        self.start = []
        self.end = []
        self.profit = []
        for i, j, k in temp:
            self.start.append(i)
            self.end.append(j)
            self.profit.append(k)
        
        print(temp)
        # get the next start which is >= this end
        def get_next(i):
            ll = i + 1
            ul = len(self.start) - 1
            ans = -1
            while ll <= ul:
                mid = ll + (ul-ll)//2
                if self.start[mid] >= self.end[i]:
                    ans = mid
                    ul = mid - 1
                else:
                    ll = mid + 1
            print(f"getting next of {i} = {ans}")
            return ans


        @lru_cache(None)
        def rec(i):
            if i >= len(self.start):
                return 0
            ans = 0
            # take this
            next_gte_i = get_next(i)
            if next_gte_i != -1:
                ans = self.profit[i] + rec(next_gte_i)
            else:
                ans = self.profit[i]
            
            # do not take this
            ans = max(
                ans, 
                rec(i+1)
            )

            print(f"for {i} returning {ans}")
            return ans

        return rec(0)

87159