0826.安排工作以达到最大收益.md

解题关键点

• 算法 1
  • 工作难度和工作收益是相关联的，所以按照工作收益从大到小排列，然后遍历工人找到第一个难度匹配的工作，把收益累加就可以了。
  • 这个算法的时间复杂度是O(n*logn + n*m)
• 算法 2
  • 按照工作难度进行排序，然后更新每个工作难度下的最大收益（如果更简单的工作收益更高，则覆盖掉原有收益），最后遍历工人，用二分查找找到可执行的最高难度的任务即可
  • 这个算法的时间复杂度是 O(n*logn + m*logn)

代码

// 这里定义了一个Work结构用于辅助排序
struct Work {
    difficulty: i32,
    profit: i32,
}
impl Work {
    pub fn new(difficulty: i32, profit: i32) -> Self {
        Work {
            difficulty,
            profit,
        }
    }
}

impl Solution {
    pub fn max_profit_assignment(difficulty: Vec<i32>, profit: Vec<i32>, worker: Vec<i32>) -> i32 {
        let mut works: Vec<Work> = Vec::new();
        for i in 0..difficulty.len() {
            // 首先创建 works 列表
            works.push(Work::new(difficulty[i], profit[i]));
        }
        // 对 works 进行排序
        // sort_by(|a, b|) 拿到 a 和 b 两个虚拟变量，然后 a.cmp(b) 按照从小到大排列，b.cmp(a) 按照从大到小排列
        works.sort_by(|a, b| b.profit.cmp(&a.profit));
        let mut res: i32 = 0;
        // 遍历工人（因为每个任务可以做多次，所以工人无需排序）
        for i in worker {
            // 'tag: 用于作为循环的标签
            'inner: for j in &works {
                if j.difficulty <= i {
                    res += j.profit;
                    // break 内部循环
                    break 'inner;
                }
            }
        }
        res
    }
}

优化了一下，改用元组代替自定义结构，代码简洁了不少

impl Solution {
    pub fn max_profit_assignment(difficulty: Vec<i32>, profit: Vec<i32>, worker: Vec<i32>) -> i32 {
        let mut works: Vec<(i32, i32)> = Vec::new();
        for i in 0..difficulty.len() {
            works.push((difficulty[i], profit[i]));
        }
        works.sort_by(|a, b| b.1.cmp(&a.1));
        let mut res: i32 = 0;
        for i in worker {
            for j in &works {
                if j.0 <= i {
                    res += j.1;
                    break;
                }
            }
        }
        res
    }
}

算法 2 的代码

// 作为挑战，自己手撸了一个快排，同时对两个向量进行排序，这样可以降低空间复杂度，不过貌似时间复杂度更高了
pub fn fast_sort(v1: &mut std::vec::Vec<i32>, v2: &mut std::vec::Vec<i32>, start: usize, end:usize) {
    let mut k = start;
    for j in (start + 1)..end {
        if v1[j] < v1[k] {
            // .swap() 用于向量交换两个位置的值
            v1.swap(j, k);
            v2.swap(j, k);
            v1.swap(j, k + 1);
            v2.swap(j, k + 1);
            k = k + 1;
        }
    }
    if start < k {
        fast_sort(v1, v2, start, k);
    }
    if k < end - 1 {
        fast_sort(v1, v2, k + 1, end);
    }
}

impl Solution {
    pub fn max_profit_assignment(mut difficulty: Vec<i32>, mut profit: Vec<i32>, worker: Vec<i32>) -> i32 {
        let len = difficulty.len();
        fast_sort(&mut difficulty, &mut profit, 0, len);
        // 动态规划，获取当前难度下 profit 的最大值
        for i in 1..profit.len() {
            // core::cmp::max 类似 JS 的 Math.max，如果要对比两个复杂数据，用 max_by()
            let max_p = core::cmp::max(profit[i], profit[i - 1]);
            // 向量在具体位置设置值可以用类似 js 的语法
            profit[i] = max_p;
        }
        let mut res: i32 = 0;
        'outer: for i in worker {
            // 解构赋值语法
            let (mut l, mut r, mut mid) = (0, difficulty.len(), difficulty.len() / 2);
            // 二分查找，loop 将启动一个死循环
            loop {
                if i < difficulty[mid] {
                    if r == l {
                        continue 'outer;
                    }
                    r = mid;
                    mid = (l + r) / 2;
                } else {
                    if mid == r - 1 || i < difficulty[mid + 1] {
                        res += profit[mid];
                        continue 'outer;
                    }
                    l = mid;
                    mid = (l + r) / 2;
                }
            }
        }
        res
    }
}

算法2，结合元组，达到了最佳运行时间

impl Solution {
    pub fn max_profit_assignment(mut difficulty: Vec<i32>, mut profit: Vec<i32>, mut worker: Vec<i32>) -> i32 {
        let mut works: Vec<(i32, i32)> = Vec::new();
        for i in 0..difficulty.len() {
            works.push((difficulty[i], profit[i]));
        }
        works.sort_by(|a, b| a.0.cmp(&b.0));

        for i in 1..works.len() {
            if works[i].1 < works[i - 1].1 {
                works[i].1 = works[i - 1].1;
            }
        }
        let mut res: i32 = 0;
        'outer: for i in worker {
            let (mut l, mut r, mut mid) = (0, works.len(), works.len() / 2);
            loop {
                if i < works[mid].0 {
                    if r == l {
                        continue 'outer;
                    }
                    r = mid;
                    mid = (l + r) / 2;
                } else {
                    if mid == r - 1 || i < works[mid + 1].0 {
                        res += works[mid].1;
                        continue 'outer;
                    } else {
                        l = mid;
                        mid = (l + r) / 2;
                    }
                }
            }
        }
        res
    }
}

测试用例

assert_eq!(max_profit_assignment(vec![2,4,6,8,10], vec![10,20,30,40,50], vec![4,5,6,7]), 100);
assert_eq!(max_profit_assignment(vec![2,4,6,8,10], vec![50,40,30,20,10], vec![4,5,6,7]), 200);
assert_eq!(max_profit_assignment(vec![2,4,6,8,10], vec![10,20,30,40,50], vec![0]), 0);