Example: Weighted Job scheduling

You are given several jobs each with a start and end time and a profit. Given than the jobs may overlap, you are tasked to determine the maximum profit.

• First, you sort the jobs by end time
• job = [start, end, profit]
• After initializing each d cell to the profit of a job. You increment i each time checking which non overlapping combination gives the maximum profit.
• You can use that in the future, once you see that a cell fits you already know the maximum job from that cell

(1,3)	(2,5)	(4,6)	(6,7)	(5,8)	(7,9)
5	6	5	5	4	11

jobSchedule(jobs)
    n = jobs.len
    let d[0..n], p[0..n] be two array as long as the input array

    sortByEndTime(jobs)
    
    for i = 0 to n-1
        d[i] = jobs[i].profit
        p[i] = -1 

    // the search can be optimized to use binary search to find the last non overlapping job before the current job under examination
    for i = 1 to n-1
        // option 1: skip current job
        d[i] = d[i-1]
        p[i] = p[i-1]

        // option 2: include current job
        j = findLastNonOverlapping(jobs, i)
        q = jobs[i].profit
        if j != -1
            q += d[j]
        
        // chose better option
        if q > d[i]
            d[i] = q
            p[i] = j

    maxProfit = d[n-1]
    print("Max Profit: " + maxProfit)
    

    schedule = Stack()   
    i = n-1
    while (i >= 0) {
        if i == 0 || d[i] != d[i-1] // job contributes to max
            schedule.push(i)
            i = p[i]
        else
            i -= 1
    }
    print("schedule:")
    while schedule not empty {
        print(schedule.pop())
    }

// Helper function to find the last non-overlapping job
    function findLastNonOverlapping(jobs, i):
        low = 0
        high = i - 1
        while low <= high:
            mid = (low + high) / 2
            if jobs[mid].end <= jobs[i].start:
                if mid == high || jobs[mid+1].end > jobs[i].start:
                    return mid
                low = mid + 1
            else:
                high = mid - 1
        return -1