package daily.hard

import java.util.*
import kotlin.Comparator
import kotlin.math.max

fun main() {
    // 1235. 规划兼职工作
    // https://leetcode.cn/problems/maximum-profit-in-job-scheduling/
    println(jobScheduling1(intArrayOf(1,2,3,3), intArrayOf(3,4,5,6), intArrayOf(50,10,40,70)))
    println(jobScheduling1(intArrayOf(1,2,3,4,6), intArrayOf(3,5,10,6,9), intArrayOf(20,20,100,70,60)))
    println(jobScheduling1(intArrayOf(1,1,1), intArrayOf(2,3,4), intArrayOf(5,6,4)))
    println(jobScheduling1(intArrayOf(1,2,2,3), intArrayOf(2,5,3,4), intArrayOf(3,4,1,2)))
}

fun jobScheduling1(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
    // 考虑【选】还是【不选】，即要不要做第 i 号工作
    val jobs = Array(startTime.size) {
        Job(startTime[it], endTime[it], profit[it])
    }
    // 根据 endTime 对任务排序
    Arrays.sort(jobs, object : Comparator<Job> {
        override fun compare(p0: Job?, p1: Job?): Int {
            return p0!!.et.compareTo(p1!!.et)
        }
    })
    val dp = IntArray(startTime.size)
    dp[0] = jobs[0].pt
    for (i in 1 until startTime.size) {
        var j = i-1
        var prev = -1
        while (j >= 0) {
            // 向前寻找“最近的”“已完成的"兼职工作
            if (jobs[i].st >= jobs[j].et) {
                prev = j
                break
            }
            j--
        }
        // “最近的”“已完成的"兼职工作的最大报酬
        val prevMaxProfit = if (prev >= 0) {
            dp[prev]
        }else {
            0
        }
        // 【选】第 i 个工作的报酬，就是 “最近的”“已完成的"兼职工作的最大报酬 + 本个工作的报酬jobs[i].pt
        val selectProfit = prevMaxProfit + jobs[i].pt
        // 【不选】第 i 个工作的报酬，那就是上一个工作的最大报酬
        val noSelectProfit = dp[i-1]
        dp[i] = max(selectProfit, noSelectProfit)
    }
    return dp[dp.size-1]
}

class Job(val st:Int, val et:Int, val pt:Int)

fun jobScheduling(startTime: IntArray, endTime: IntArray, profit: IntArray): Int {
    // 考虑【选】还是【不选】，即要不要做第 i 号工作
    /**
     * 1. 状态定义
     * dp[i] 表示前 i+1 个任务的最优解
     * 2. 转移方程
     * 2.1 【选】第 i 号工作：dp[i] = profit[i] + dp[prev[i]]，prev[i] 表示在【选】了第 i 号工作的情况下，前一个能【选】的工作的序号
     * 2.2 【不选】第 i 号工作：dp[i] = dp[i-1]
     * 所以 dp[i] = max(profit[i] + dp[prev[i]], dp[i-1])
     * 3. 初始值
     * dp[0] = profit[0]
     */
    // 根据 endTime 对任务排序，endTimeSortedIndex[0] 表示结束时间最小的工作序号，endTimeSortedIndex[1] 表示结束时间最大的工作序号
    val endTimeSortedIndex = Array(endTime.size) {
        it
    }
    Arrays.sort(endTimeSortedIndex, object : Comparator<Int>{
        override fun compare(p0: Int?, p1: Int?): Int {
            return endTime[p0!!].compareTo(endTime[p1!!])
        }
    })

    val prevArray = IntArray(endTime.size) {
        -1
    }
    // 填充 prevArray 数组，prev[i] 表示在【选】了第 i 号工作的情况下，前一个能【选】的工作的序号
    for (i in endTimeSortedIndex.indices) {
        val jobIndex = endTimeSortedIndex[i]
        val curStartTime = startTime[jobIndex]
        // endTimeSortedIndex 从后往前找，找第一个 endTime 小于等于 curStartTime 的任务需要，就是 prev[i]
        var j = jobIndex-1
        while (j >= 0) {
            if (curStartTime >= endTime[endTimeSortedIndex[j]]) {
                prevArray[jobIndex] = endTimeSortedIndex[j]
                break
            }
            j--
        }
    }
    val dp = IntArray(endTime.size)
    dp[0] = profit[endTimeSortedIndex[0]]
    for (i in 1 until endTimeSortedIndex.size) {
        val jobIndex = endTimeSortedIndex[i]
        // 选第 i 个工作的报酬
        // 前一份工作能拿到的最优报酬
        val prevMaxProfit = if (prevArray[jobIndex] == -1) {
            0
        }else {
            dp[prevArray[jobIndex]]
        }
        val selectProfit = profit[jobIndex] + prevMaxProfit
        // 不选第 i 个工作的报酬，就是 dp[i-1] 了
        val noSelectProfit = dp[jobIndex -1]
        dp[jobIndex] = max(selectProfit, noSelectProfit)
    }
    return dp[dp.size - 1]
}