P1235 - Maximum Profit in Job Scheduling

Problem Abstraction

Given 3 arrays, startTime and endTime and profit, find the maximum profit you can take such that there no two jobs in the subset with overlapping time range.

Perspectives:

1. 从某个时刻开始, 选择哪些任务去做(以startTime来考虑, 存在后效性, 无法进行有效的DP)
2. 考虑第i个任务, 选择或者不选(以endTime来考虑, 不存在后效性, 可以进行有效的DP)

Conclusions

第2种视角

定义f[i]表示按照时间结束顺序排序后, 前i个工作所能获得的最大报酬.

分类讨论:

1. 不选择第i个工作: f[i] = f[i - 1]
2. 选择第i个工作: $f[i]=ma{x}_j(f[j]+profit[i])$, in which endTime[j] <= startTime[i], 即小于i, 且满足条件的最大的j.

Code

/// dp in O(nlogn)/O(n)
pub fn job_scheduling2(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
    let n = start_time.len();

    let mut jobs = Vec::with_capacity(n);

    for i in 0..n {
        jobs.push((end_time[i] as usize, start_time[i] as usize, profit[i]));
    }

    jobs.sort_unstable();

    let mut f = vec![0; n + 1];
    f[0] = 0;
    for i in 0..n {
        let j = upper_bound(&jobs[0..i], jobs[i].1);
        f[i + 1] = f[i].max(f[j] + jobs[i].2);
    }

    f[n]
}

/// run in O(logn)
fn upper_bound(jobs: &[(usize, usize, i32)], time: usize) -> usize {
    use std::cmp::Ordering::{Greater, Less};
    match jobs.binary_search_by(|i| if i.0 <= time { Less } else { Greater }) {
        Ok(idx) => unreachable!(), // we are not return Equal in the closure
        Err(idx) => idx,
    }
}