LeetCode Entry

1235. Maximum Profit in Job Scheduling

26.11.2022 hard 2022 kotlin

fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {

1235. Maximum Profit in Job Scheduling hard

https://t.me/leetcode_daily_unstoppable/32

    fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
        val n = startTime.size
        val inds = Array<Int>(n) { it }
        inds.sortWith (Comparator<Int> { a, b ->
            if (startTime[a] == startTime[b])
                endTime[a] - endTime[b]
            else
                startTime[a] - startTime[b]
        })
        val maxProfit = IntArray(n) { 0 }
        maxProfit[n-1] = profit[inds[n-1]]
        for (i in n-2 downTo 0) {
            val ind = inds[i]
            val end = endTime[ind]
            val prof = profit[ind]

            var lo = l + 1
            var hi = n - 1
            var nonOverlapProfit = 0
            while (lo <= hi) {
                val mid = lo + (hi - lo) / 2
                if (end <= startTime[inds[mid]]) {
                    nonOverlapProfit = maxOf(nonOverlapProfit, maxProfit[mid])
                    hi = mid - 1
                } else lo = mid + 1
            }
            maxProfit[i] = maxOf(prof + nonOverlapProfit, maxProfit[i+1])
        }
        return maxProfit[0]
    }

Use the hints from the description. THis cannot be solved greedily, because you need to find next non-overlapping job. Dynamic programming equation: from last job to the current, result is max of next result and current + next non-overlapping result.

f(i) = max(f(i+1), profit[i] + f(j)), where j is the first non-overlapping job after i.

Also, instead of linear search for non overlapping job, use binary search.

O(NlogN) time, O(N) space