InOrderTaskSchedule

Task Scheduler
1.每个task运行完后有m个cool down period，在这期间不可以运行同样的task
2.cooldown period里可以随便运行其他的task
3.不能改变运行的顺序

例题：
[1, 1, 2, 1, 2] M = 2

运行方式：
1 _ _ 1 2 _ 1 2
output: 8 （需要8个time unit）

followup：
如果m远远小于k（k是task种类数，怎么优化）
用lru cache优化。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include "misc.h" class Solution{ public: int getLength(vector<int>& s, int m){ map<int, int> mp;//task, index int ts = 0; for(int i=0; i<s.size(); ++i){ int task = s[i]; if(mp.count(task)!=0 && ts-mp[task]-1<m){ ts = mp[task]+m+1; } mp[task] = ts++; } return ts; } }; //if task types >> m class Solution1{ public: int getLength(vector<int>& s, int m){ map<int, int> mp;//task, timestamp int ts = 0; for(int i=0; i<s.size(); ++i){ int task = s[i]; if(mp.count(task)!=0 && ts-mp[task]-1<m){ ts = mp[task]+m+1; } mp[task] = ts++; if(mp.size()>m){ priority_queue<pair<int, int>> pq;//timestamp, task for(auto p:mp){ pq.emplace(-p.second, p.first); } int taskToBeRemoved = pq.top().second; mp.erase(taskToBeRemoved); } } return ts; } }; int main(){ Solution sol; Solution1 sol1; vector<int> task{1,1,2,1,2,4,6,8,4,3,4,6,4,4,2,4,5,2}; cout<<sol.getLength(task, 4)<<endl; cout<<sol1.getLength(task, 4)<<endl; return 0; }

• yimusanfen