<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>

'''
n jobs
each job runs from start[i] to end[i] (not inclusive, so end + start at the same time is ok)
each job has profit profit[i]

Want to know: what's the maximum profit that you can obtain by running jobs that don't overlap?

Naive solution is at least O(2^n), so that's obviously not ok. We need to find some structure.

Suppose we think about building up the job list by choosing our jobs one at a time, from left to right.
- *this* is the first job. What's the best we can get if this is the first job?
- then that will take up some block of time, ending at end[i].
- and then we just want to know... what's the best we can do if we only pick jobs that start on/after end[i]?
- we filter the jobs to the ones that satisfy that criteria
- and then we just compute their best_if_start value.

The time complexity will be...
- O(n) to loop over each of the starting jobs.
- O(n) for each of those to iterate over the jobs that start after our end.
- --> O(n^2) in total.

Can we do better? Seems like closer to O(n) is possible.

For example:
- Sort the jobs in order of start time.
- Iterate from *latest* to *earliest* start time.
    - Hmm, that doesn't quite help us. Let's draw an example:

Let's go with the O(n^2) solution and then try to optimize it.

Ok, cool. That gets TLE.
The slow part is looping over all of the neighbors.
We need a fast way to figure out 2 things:
1. What are all the jobs that start after a certain point
    - Sort + binary search could get that part to O(log n)
2. What is the best profit that I can get from jobs that start on/after time T?

[  ] [  ] [  ]
         [       ]

My cache stores the best profit that I can get from jobs that start at time start[i].
At least, I could index it that way...

But then I still need to do a linear scan over the cache to go over all the values with start greater than my end...

I see two possible options here...
1. Find some clever way to sort this or greedy strategy to further optimize.
2. Use a sorted deque and binary search over that deque.

For example...
Suppose that our deque stores:
    (start[i], best_starting_at)
We want to know... what's the best we can get if we start on / after X.

So we want to maintain the following invariants:
1. Sorted in order of start values.
2. Only keep best_starting_at values in strictly increasing order.
    - No need to keep an entry if the right entries have a later start *and* a worse best_starting_at.

We will start by sorting the list by start time.
We'll iterate from latest to earliest start time.
Insertion into the deque is amortized O(1) per op.
Accessing the deque is O(log n).

That gets us to O(n log n) total.

Hopefully is good enough.
'''

def best_starting_at(start: list[int], end: list[int], profit: list[int], i: int, cache: dict[int, int]) -> int:
    if i in cache:
        return cache[i]
    
    res = 0
    for j in range(len(start)):
        if start[j] >= end[i]:
            res = max(res, best_starting_at(start, end, profit, j, cache))

    res += profit[i]

    cache[i] = res
    return res

'''
res = 0
cache = {}
for i in range(len(startTime)):
    best_from_i = best_starting_at(startTime, endTime, profit, i, cache)
    res = max(res, best_from_i)
return res
'''

from typing import Callable

def search_sorted(n: int, f: Callable[[int], int]) -> int:
    lo = 0 # lo - 1 is false
    hi = n # hi is true

    while lo != hi:
        mid = (lo + hi) // 2
        if f(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        jobs = list(zip(startTime, endTime, profit))
        jobs.sort(key = lambda tup: (tup[0], -tup[2]))

        n = len(jobs)

        # jobs is now sorted in ascending order of start time
        res = 0
        s = []
        for i in range(len(jobs) - 1, -1, -1):
            start_i, end_i, profit_i = jobs[i]

            # search the deque
            stack_idx = search_sorted(
                len(s),
                # stack is sorted in descending order of start times.
                # If normal sorting... I want to find the first entry with start >= end_i
                # Since we have reverse sorting... I can just search in reverse order.
                lambda j: s[len(s) - j - 1][0] >= end_i
            )
            stack_idx = len(s) - stack_idx - 1

            # if there are no such values... deque_idx = -1
            if stack_idx >= 0:
                best_in_stack = s[stack_idx][1]
            else:
                best_in_stack = 0

            best_from_i = profit_i + best_in_stack 
            res = max(res, best_from_i)

            # update the stack
            # The stack will automatically remain in order of start index
            # I don't want to add a value that's smaller 
            if not s or s[-1][1] < best_from_i:
                s.append((start_i, best_from_i))
        return res
912