这道面试题是从 HarrisonHao 的一篇博文中看到的:
我看到之后,感觉此题十分有趣,遂自己用 node.js 以不同的思路实现了一遍,实现中使用了 lodash
原题比较长,而且是英文的,就不粘过来了,完整题目和代码可见 {aa0aa}
用 HarrisonHao 的话说,就是要把 19 个给定大小的萝卜放进 4 个给定大小的坑里,坑可以没占满,但萝卜不能剩下。
先把清单中的议题按照占用时间排序,方便后续操作,然后开始往时间段中安排,每次拿出一个最耗时的议题,放入最空闲的时段中,不断循环,直到所有议题都被安排进去;
本次是在 node.js 中实现的,使用 fs 模块读取文件,按行分割后,将每行内容转为一个 Talk 对象,并按占用时间进行排序:
- const fs = require('fs');
- const _ = require('lodash');
- //会议类
- class Talk {
- constructor (line) {
- const words = _.compact(line.split(' '));
- const duration = words.pop();
- if (isNaN(duration[0])) {
- words.push(duration)
- this.duration = 5;
- } else {
- this.duration = duration.slice(0, -4);
- }
- this.name= words.join(' ')
- }
- }
- //获得输入参数
- const args = process.argv.splice(2);
- const [inputPath, outputPath] = args;
- //读取输入文件内容
- let input = fs.readFileSync(inputPath, 'utf8')
- //分割输入文件内容
- input = _.compact(input.split('\r').join().split('\n'));
- //生成会议列表
- let talks = input.map(line=>new Talk(line));
- //按占用时间从小到大排序
- talks = _.orderBy(talks, 'duration');
Slot 类实例化时接收一个总可用分钟数,并包含三个方法:
add: 将一个议题添加进该时间段,
used: 返回已使用的分钟数,
balance: 返回空闲的分钟数
每天上午有 3 个小时会议时间即 180 分钟,下午 240 分钟,所以我们可以直接用这两个分钟数来生成时间段:
- //时间段类
- class Slot {
- constructor (limit) {
- this.limit = limit;
- this.list = [];
- };
- //剩余可用分钟数
- balance () {
- return this.limit - this.used()
- };
- //已安排掉的分钟数
- used () {
- let used = 0;
- this.list.forEach((talk)=>{
- used += (talk.duration-0)
- });
- return used;
- };
- add (talk) {
- this.list.push(talk)
- }
- }
- //生成时间段列表
- let slots = [180, 240, 180, 240].map(limit=>new Slot(limit));
现在要把萝卜往坑里扔了,之前提到思路是每次把耗时最长的议题扔进最空闲的时间段中,不断循环,直到所有议题 (萝卜) 都安排进时间段 (坑) 里;
获取耗时最长的议题很简单,因为我们之前已经给议题排序了,每次只要
弹出最后一条议题就可以了; 获取最空闲的时间段也是一样的原理,用上 Slot 对象的 balance 方法,按照空闲时间倒序排序,排序结果的第一条就是最空闲的时间段;
- .pop()
- //分配会议
- function arrange (talks, slots) {
- //拿出一个占用时间最长的会议
- const talk = talks.pop();
- //放到时间最富裕的时间段内
- slots = _.orderBy(slots, slot=>slot.balance(), 'desc');
- slots[0].add(talk);
- if (talks.length == 0) return slots;
- return arrange(talks, slots);
- };
- //分配每个会议到各个时间段内
- const result = arrange(talks, slots);
反正原题似乎是要求按一定格式输出的…… 不过格式这种东西就不细说了,上个代码得了……
- //格式化输出
- function print (slots) {
- const formatNum = (num)=>('0'+num).slice(-2);
- const am = {}, pm = {};
- [am[1],am[2],pm[1],pm[2]] = _.orderBy(slots, 'limit');
- [1,2].forEach((i)=>{
- let minutes;
- console.log('Track '+i);
- minutes = 9*60
- am[i].list.forEach((talk)=>{
- const h = formatNum(Math.floor(minutes/60));
- const m = formatNum(minutes%60);
- const outputLine = [
- h,':',m,'AM',' ',
- talk.name,' ',talk.duration,'min'
- ].join('');
- console.log(outputLine);
- minutes += talk.duration-0;
- })
- console.log('12:00PM Lunch');
- minutes = 1*60
- pm[i].list.forEach((talk)=>{
- const h = formatNum(parseInt(minutes/60));
- const m = formatNum(minutes%60);
- const outputLine = [
- h,':',m,'PM',' ',
- talk.name,' ',talk.duration,'min'
- ].join('');
- console.log(outputLine);
- minutes += talk.duration-0;
- })
- console.log('05:00PM Networking Event');
- })
- }
- print(slots);
- λ node conference.js input.txt
- Track 1
- 09:00AM Clojure Ate Scala (on my project) 45min
- 09:45AM Pair Programming vs Noise 45min
- 10:30AM Overdoing it in Python 45min
- 11:15AM Lua for the Masses 30min
- 11:45AM Rails for Python Developers lightning, 5min
- 12:00PM Lunch
- 01:00PM Ruby on Rails: Why We Should Move On 60min
- 02:00PM Rails Magic 60min
- 03:00PM Ruby Errors from Mismatched Gem Versions 45min
- 03:45PM User Interface CSS in Rails Apps 30min
- 04:15PM Woah 30min
- 05:00PM Networking Event
- Track 2
- 09:00AM Writing Fast Tests Against Enterprise Rails 60min
- 10:00AM Accounting-Driven Development 45min
- 10:45AM Ruby vs. Clojure for Back-End Development 30min
- 11:15AM Programming in the Boondocks of Seattle 30min
- 12:00PM Lunch
- 01:00PM Ruby on Rails Legacy App Maintenance 60min
- 02:00PM Communicating Over Distance 60min
- 03:00PM Common Ruby Errors 45min
- 03:45PM A World Without HackerNews 30min
- 04:15PM Sit Down and Write 30min
- 05:00PM Networking Event
虽然是实现了效果,但我感觉还不完善,现在这种算法还很简单,原题本身就富裕了 55 分钟的时间,所以才能用这种方式实现,如果占的更满就不一定好使了,以后我会再继续尝试改进;
如果有更好的思路也欢迎告诉我,我也会试着实现一下的~
来源: http://www.cnblogs.com/Eden-cola/p/javascript-conference-track-management.html