任务调度(离散化版本)

作者: | 更新日期:

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

零、前言

昨天写了一篇文章《Leetcode 要封杀中文题解了》吐槽一下 leetcode。

当然,在别人的地盘上,自然需要按别人的规则做事。
所以 leetcode 那样做也没有错。

至于未来,是否在 leetcode 写英文的题解,我还没想好。
毕竟之前写中文是给国内人看的,写英文的话,那么多题解,别人为什么看我的呢?
这个我再想想。

一、背景

在《Leetcode 第 159 场比赛回顾》文章中提到,最后一题我花费了十几分钟使用动态规划过得。

PS:建议先去看看那道题的意思与题解。
这篇文章是上篇文章的扩展,顺便分享一些高级算法。

题意很简单,给一些时间区间,每个区间有一些奖金,求挑选一些不相交的区间,使得奖金最高。

常规思路也很简单,从最大时间开始递归。
1、选择当前结束时间,然后求选择区间后,之前时间的最优值。
2、不选择当前结束时间,则时间向前稍微偏移一点点,求之前这些时间的最优值。

对于这道题,特点就是时间范围特别大。
这就导致没办法像正规的动态规划那样递归了。

二、基本思路

简单分析后,可以发现其实不需要那么大的空间来储存所有时间范围。
我们只需要把所有的结束时间点储存下来就行了,这个只有几万个。

所以我第一个方法是使用时间的下标来当做状态,这样就只有几万个状态,可以储存下来了。

状态的空间问题解决了,接下来就是递归时怎么找到子问题下标了。

我的第一个方法是通过二分查找,log(n)的复杂度找到子问题下标,从而能够解决这道问题。

三、离散化

其实,面对状态非常大的问题,还有一个高级用法,那就是离散化。
离散化后,我们就可以通过下标的偏移来找到下一个状态了。

这种思想最经典的实践就是多个矩阵的周长与面积。
而理解了离散化的原理后,我们可以发现,凡是这种少数数据范围很大时,都可以用这种方法来压缩空间。

那怎么离散化呢?
其实很简单。

1、第一步统计所有的时间点。
2、第二步从小到大给每个时间点分配一个递增编号。

这样,我们就可以通过下标索引的操作,快速找到上一个时间点。

map<LL, int> timeToIndex; //时间离线化的编号
map<int, LL> indexToTime; //编号对应的时间

for(int i=0;i<l;i++){
    timeToIndex[startTime[i]] = 0;
    timeToIndex[endTime[i]] = 0;
}
int index = 0;
for(auto& p : timeToIndex){
    p.second = ++index;
    indexToTime[index] = p.first;
}

大概代码就想上面那样,使用map还是vector根据个人爱好来实现就行了。
以前我都用vector排序,现在更喜欢使用map

离散化之后,数据量太大的问题就不存在了。
然后就是索引得到时间、时间得到下标,然后就可以转移状态了。

四、最后

这篇文章介绍的比较抽象了。
后面有机会与时间,会详细的讲解一下离散化。

如果有机会,这道题的另外一种做法也分享给大家,有缘再见吧。

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越