CodingTour
ARTS #182

Algorithm

本周选择的算法题是:Maximum Profit in Job Scheduling

规则

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

img

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
Explanation: The subset chosen is the first and fourth job. 
Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

img

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
Explanation: The subset chosen is the first, fourth and fifth job. 
Profit obtained 150 = 20 + 70 + 60.

Example 3:

img

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6

Constraints:

  • 1 <= startTime.length == endTime.length == profit.length <= 5 * 104
  • 1 <= startTime[i] < endTime[i] <= 109
  • 1 <= profit[i] <= 104

Solution

impl Solution {
    pub fn job_scheduling(start_time: Vec<i32>, end_time: Vec<i32>, profit: Vec<i32>) -> i32 {
        let mut jobs = start_time
            .into_iter()
            .zip(end_time.into_iter())
            .zip(profit.into_iter())
            .map(|((start, end), profit)| (start, end, profit) )
            .collect::<Vec<_>>();
        
        jobs.sort_by_key(|job| job.1);
        
        let n = jobs.len();
        let mut dp = vec![0; n];
        dp[0] = jobs[0].2;
        for i in 1..n {
            dp[i] = jobs[i].2.max(dp[i-1]);
            for j in (0..=i-1).rev() {
                if jobs[j].1 <= jobs[i].0 {
                    dp[i] = dp[i].max(dp[j] + jobs[i].2);
                    break;
                }
            }
        }

        dp.iter().max().unwrap().clone()
    }
}

Review

Rust is the future of Front-End development

最近有一个有趣的说法:任何能够用 Rust 实现的应用系统,最终都必将用 Rust 实现。该说法模仿的是 Atwood 定律,背后一个正在发生的事是 Rust 正迅速占领基础设施领域,比如使用 Rust 开发的前端构建工具,在性能上比传统流行的工具有数倍的提升。

之所以这类工具选择用 Rust 开发/重写,无外乎两个原因:高性能,Rust 有惊人的内存利用率,以及零成本抽象;可靠性,Rust 丰富的类型系统和所有权模型保证了内存安全和线程安全,让你在编译期就能够消除各种各样的错误。

目前 Rust 呈现出的这种趋势有些不可阻挡,希望我们团队也能尽早吃上 Rust 这只螃蟹。

Tip

Y Combinator 的项目,一个号称比 Arc 更注重卡片、分类、空间的管理的浏览器:SigmaOS,由于采用 Swift 开发,应用体积只有 25M,作为对比,Arc 高达 650M。

喜欢尝新的朋友可以试试看。

Share

分享几个正则表达式相关的工具~

Regex Learn

游戏化学习正则表达式的工具,体验和反馈做的不错,可能是最好的入门工具之一:

regex101

在线测试正则表达式的工具,除了展示匹配结果以外,还会拆解表达式的各个组成部分,直观的查看匹配过程:

Regexper

正则表达式可视化工具,示例:git 分支名匹配

^refs\/heads\/(featurebugfixhotfixbetarelease)\/[\/a-zA-Z0-9._-]+$

AutoRegex

一个用深度学习实现的将自然语言转成正则表达式的工具:

RegEX 备忘清单

来自一份国产的速查表:

最后

对程序员来说,正则表达式是一项非常基础而有用的技能,两个理由:

  1. 总有一天 RegEx 会是手头某个问题的最佳解决方案
  2. 当你在别人的代码中看到正则表达式时,它不是神秘的代码

如果你想更系统性的学习正则表达式,不妨看看 《精通正则表达式》第3版。