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:
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:
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:
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\/(feature bugfix hotfix beta release)\/[\/a-zA-Z0-9._-]+$
AutoRegex
一个用深度学习实现的将自然语言转成正则表达式的工具:
RegEX 备忘清单
来自一份国产的速查表:
最后
对程序员来说,正则表达式是一项非常基础而有用的技能,两个理由:
- 总有一天 RegEx 会是手头某个问题的最佳解决方案
- 当你在别人的代码中看到正则表达式时,它不是神秘的代码
如果你想更系统性的学习正则表达式,不妨看看 《精通正则表达式》第3版。