Maximum Profit in Job Scheduling

Problem statement

You have n jobs. Job i runs from startTime[i] to endTime[i] and pays profit[i]. You may schedule any subset of jobs as long as no two chosen jobs overlap in time (an end time of t is compatible with a later start of t). Return the maximum total profit you can earn.

Example:

Input:

startTime = [1, 2, 3, 3]
endTime   = [3, 4, 5, 6]
profit    = [50, 10, 40, 70]

Expected output:

Why: take the first job (50) and the last job (70).

Practice on LeetCode: Maximum Profit in Job Scheduling

Golang Solution

Bundle each job, sort by end time, then DP: for job i, choose max of skipping it (dp[i-1]) or taking it plus the best profit among jobs that finish by jobs[i].start (found with binary search).

Time: O(n log n) — sort plus a binary search per job
Space: O(n) — jobs slice and DP array

func jobScheduling(startTime []int, endTime []int, profit []int) int {
    jobs := make([]Jobs, len(profit))

    for i := 0; i < len(profit); i++ {
        jobs[i] = Jobs{
            start:  startTime[i],
            end:    endTime[i],
            profit: profit[i],
        }
    }

    // Sort by end time
    sort.Slice(jobs, func(i, j int) bool {
        return jobs[i].end < jobs[j].end
    })

    dp := make([]int, len(jobs))
    dp[0] = jobs[0].profit

    for i := 1; i < len(jobs); i++ {
        // Don't take current job
        notTake := dp[i-1]

        // Take current job
        take := jobs[i].profit

        // Find latest compatible job
        j := findPrevJob(jobs, i)

        if j != -1 {
            take += dp[j]
        }

        dp[i] = max(take, notTake)
    }

    return dp[len(jobs)-1]
}

type Jobs struct {
    start  int
    end    int
    profit int
}

func findPrevJob(jobs []Jobs, i int) int {
    low := 0
    high := i - 1
    answer := -1

    for low <= high {
        mid := low + (high-low)/2

        if jobs[mid].end <= jobs[i].start {
            answer = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    return answer
}