频道栏目
首页 > 考试 > 其他 > 正文

编程开发Task Scheduler问题解析

2018-06-28 14:09:05         来源:Pilgrim  
收藏   我要投稿

编程开发Task Scheduler问题解析。这道题让我们安排CPU的任务,规定在两个相同任务之间至少隔n个时间点。说实话,刚开始博主并没有完全理解题目的意思,后来看了大神们的解法才悟出个道理来。下面这种解法参考了大神fatalme的帖子,由于题目中规定了两个相同任务之间至少隔n个时间点,那么我们首先应该处理的出现次数最多的那个任务,先确定好这些高频任务,然后再来安排那些低频任务。如果任务F的出现频率最高,为k次,那么我们用n个空位将每两个F分隔开,然后我们按顺序加入其他低频的任务,来看一个例子:


AAAABBBEEFFGG 3

我们发现任务A出现了4次,频率最高,于是我们在每个A中间加入三个空位,如下:

A---A---A---A

AB--AB--AB--A(加入B)

ABE-ABE-AB--A(加入E)

ABEFABE-ABF-A(加入F,每次尽可能填满或者是均匀填充)

ABEFABEGABFGA(加入G)

再来看一个例子:

ACCCEEE 2

我们发现任务C和E都出现了三次,那么我们就将CE看作一个整体,在中间加入一个位置即可:

CE-CE-CE

CEACE-CE(加入A)

注意最后面那个idle不能省略,不然就不满足相同两个任务之间要隔2个时间点了。

这道题好在没有让我们输出任务安排结果,而只是问所需的时间总长,那么我们就想个方法来快速计算出所需时间总长即可。我们仔细观察上面两个例子可以发现,都分成了(mx - 1)块,再加上最后面的字母,其中mx为最大出现次数。比如例子1中,A出现了4次,所以有A---模块出现了3次,再加上最后的A,每个模块的长度为4。例子2中,CE-出现了2次,再加上最后的CE,每个模块长度为3。我们可以发现,模块的次数为任务最大次数减1,模块的长度为n+1,最后加上的字母个数为出现次数最多的任务,可能有多个并列。这样三个部分都搞清楚了,写起来就不难了,我们统计每个大写字母出现的次数,然后排序,这样出现次数最多的字母就到了末尾,然后我们向前遍历,找出出现次数一样多的任务个数,就可以迅速求出总时间长了

 

bool cmp(const int a, const int b) {
 return a > b;
}
class Solution {
public:
 int leastInterval(vector& tasks, int n) {
  int counter[26];
  memset(counter, 0, sizeof(counter));
  for (int i = 0; i < tasks.size(); i++) {
counter[ tasks[i] - 'A' ] ++ ;
  }
  sort(counter, counter+26, cmp);
  int ret = 0, done = 0;
  int mx = counter[0];
  int i = 0;
  while (i < 26 && counter[i] == mx) i ++;
  return max((int)tasks.size(), (mx-1) * (n+1) +  i);
  // while ( done < tasks.size() ) {
  //  int cur = 0;
  //  bool first = true;
  //  for (int i = 0; i < 26; i++) {
  //if (counter[i] != 0) {
  // if (first) pos = i, first = false;
  // cur ++;
  // counter[i] --;
  // done++;
  //}
  //if (cur >= n+1) break;
  //  }
  //  if (cur < n+1 && done < tasks.size() && ( last == pos|| last == -1)) ret += n + 1 - cur;
  //  ret += cur;
  //  last = pos;
  // }
  // return ret;
 }
};
上一篇:a+b 翻译 分析 代码
下一篇:程序开发数字分类问题解析
相关文章
图文推荐
热门新闻

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站