请教F最近超爱的面试题任务安排的follow up怎么做 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教F最近超爱的面试题任务安排的follow up怎么做

请教F最近超爱的面试题任务安排的follow up怎么做# JobHunting - 待字闺中

y*e2015-04-19 07:04

1 楼

这题我第一次看到是在板上，在这里
http://www.mitbbs.com/article_t/JobHunting/32876295.html
Tasks: AABABCD
Cooldown Time: 2
A__AB_ABCD
Output: 10
后来发现这题很快变成fb的新欢，各种follow up啊。。。今天看到一个实在心塞的，
越想越复杂，想发上来问问大家有啥好主意
follow up是给你一个task队列，要求你自己排列要求最后的总时间最小，比如
aaaabbbccd，可以排成abcabcabda。
看到有人建议说每次排gap + 1个任务，取distinct tasks，也就是尽量分开同种任务
，放的时候从frequency高的开始，我觉得这就需要一个treemap了吧，先abc放完，然
后再放一轮abc，放一个减少count,count == 0的时候从treemap里去掉。如果是aaab怎
样的呢？放完ab只能再空等一次才能再放a，这样的话是不是应该有个deque来实现？

b*i2015-04-19 07:04

2 楼

刚写了一个，没有好好test，请指点：
不过好像你主要是问follow-up?那我再想想
顺便问一下，我就见过之前一次，你还在哪儿的面经看到过这个题的
class Solution {
public:
int task_scheduler(string s, int t) {
int n = s.length();
if(n == 0)
return 0;
if(t <= 0)
return n;
vector lastindex(256, -1);
int shift = 0;
for(int i = 0; i < n; i++) {
char c = s[i];
int curr = shift + i;
if(lastindex[c] != -1) {
shift += max(0, lastindex[c] + t + 1 - curr);
}
lastindex[c] = shift + i;
}
return shift + n;
}
};
int main() {
Solution solution;
cout << solution.task_scheduler("AABABCD", 2) << endl;
}

【在 y*****e 的大作中提到】

: 这题我第一次看到是在板上，在这里
: http://www.mitbbs.com/article_t/JobHunting/32876295.html
: Tasks: AABABCD
: Cooldown Time: 2
: A__AB_ABCD
: Output: 10
: 后来发现这题很快变成fb的新欢，各种follow up啊。。。今天看到一个实在心塞的，
: 越想越复杂，想发上来问问大家有啥好主意
: follow up是给你一个task队列，要求你自己排列要求最后的总时间最小，比如
: aaaabbbccd，可以排成abcabcabda。

h*32015-04-19 07:04

3 楼

感觉要用 priority queue + stack
（1）先按照每个task出现的次数建立pq
（2）如果给定的cool down time是n，那么从heap顶端poll n个元素放入stack，同时
用这n个元素建立新task的顺序
（3）再把stack中的每个元素出现次数-1，放入pq
重复只到pq为0
不知道这个想法对不对，请大家指正

h*32015-04-19 07:04

4 楼

public static String bestTime(String tasks, int cooldown){
if(tasks==null || tasks.length()==0 || cooldown<0){
throw new IllegalArgumentException("input not valid");
}
int waitTime = cooldown;
int curRep =0;
StringBuilder res = new StringBuilder();
Stack stack = new Stack();
HashMap map = new HashMap();
PriorityQueue pq = new PriorityQueue(11, new Comparator<
Task>(){
@Override
public int compare(Task a, Task b){
return b.rep - a.rep;
}
});
for(int i=0;ichar c = tasks.charAt(i);
if(map.containsKey(c)){
map.put(c, map.get(c)+1);
}else{
map.put(c, 1);
}
}
Iterator it = map.keySet().iterator();
while(it.hasNext()){
char tempChar = (Character)it.next();
Task newTask = new Task(tempChar,map.get(tempChar));
pq.offer(newTask);
}
while(pq.isEmpty()==false){
while(waitTime>=0){
Task tempTask = pq.poll();
res.append(tempTask.name);
curRep = tempTask.rep;
if(curRep>1){
tempTask.setRep(tempTask.rep-1);
stack.push(tempTask);
}
waitTime--;
if(pq.isEmpty()){
break;
}
}
waitTime = cooldown;
while(stack.isEmpty()==false){
pq.offer(stack.pop());
}
}
return res.toString();
}

public static void main(String [] args){
String str = "aababcd";
String str2 = "aaaab";
int cooldown = 2;
String best = bestTime(str,cooldown);
String best2 = bestTime(str2,cooldown);
System.out.println(best2);
}

h*32015-04-19 07:04

5 楼

把这个followup 谢了一下，请大牛指点一下对不对
task 用一个字母表示
class 定义如下，返回的是最优的task排序
public char name;
/* how many time the same task has been scheduled */
public int rep;
public Task(char name, int rep){
this.name = name;
this.rep = rep;
}
public void setRep(int rep){
this.rep = rep;
}