前两天面试ThoughtWorks，有一道家庭作业题，题目如下：
Problem Two: Conference Track Management You are planning a big programming conference and have received many proposals which have passed the initial screen process but you're having trouble fitting them into the time constraints of the day -- there are so many possibilities! So you write a program to do it for you.The conference has multiple tracks each of which has a morning and afternoon session.Each session contains multiple talks.Morning sessions begin at 9am and must finish before 12 noon, for lunch.Afternoon sessions begin at 1pm and must finish in time for the networking event.The networking event can start no earlier than 4:00 and no later than 5:00.No talk title has numbers in it.All talk lengths are either in minutes (not hours) or lightning (5 minutes).Presenters will be very punctual; there needs to be no gap between sessions. Note that depending on how you choose to complete this problem, your solution may give a different ordering or combination of talks into tracks. This is acceptable; you don’t need to exactly duplicate the sample output given here. Test input:Writing Fast Tests Against Enterprise Rails 60minOverdoing it in Python 45minLua for the Masses 30minRuby Errors from Mismatched Gem Versions 45minCommon Ruby Errors 45minRails for Python Developers lightningCommunicating Over Distance 60minAccounting-Driven Development 45minWoah 30minSit Down and Write 30minPair Programming vs Noise 45minRails Magic 60minRuby on Rails: Why We Should Move On 60minClojure Ate Scala (on my project) 45minProgramming in the Boondocks of Seattle 30minRuby vs. Clojure for Back-End Development 30minRuby on Rails Legacy App Maintenance 60minA World Without HackerNews 30minUser Interface CSS in Rails Apps 30min Test output: Track 1:09:00AM Writing Fast Tests Against Enterprise Rails 60min10:00AM Overdoing it in Python 45min10:45AM Lua for the Masses 30min11:15AM Ruby Errors from Mismatched Gem Versions 45min12:00PM Lunch01:00PM Ruby on Rails: Why We Should Move On 60min02:00PM Common Ruby Errors 45min02:45PM Pair Programming vs Noise 45min03:30PM Programming in the Boondocks of Seattle 30min04:00PM Ruby vs. Clojure for Back-End Development 30min04:30PM User Interface CSS in Rails Apps 30min05:00PM Networking Event Track 2:09:00AM Communicating Over Distance 60min10:00AM Rails Magic 60min11:00AM Woah 30min11:30AM Sit Down and Write 30min12:00PM Lunch01:00PM Accounting-Driven Development 45min01:45PM Clojure Ate Scala (on my project) 45min02:30PM A World Without HackerNews 30min03:00PM Ruby on Rails Legacy App Maintenance 60min04:00PM Rails for Python Developers lightning05:00PM Networking Event
思路如下：
把所有的会议安排在两天内，每天分为上午和下午，上午最多三小时（180min），9点到12点，下午最多四小时（240min），1点到5点。
其实就是给定大小的4个坑，每个会议都是一个固定大小的萝卜，要把这所有的19个萝卜装到4个坑中，可以装不满，但萝卜不能有剩余。
解法如下：
创建如下工程：
其中 talks-list.txt 为输入内容，如下图：
通过 FileTool 工具类将其读取到 map 中，key 为会议名称，value 为所用时间，FileTool 内容如下：
package harrison.ConferenceTrackManagement;import java.io.BufferedReader;import java.io.File;import java.io.FileReader;import java.io.IOException;import java.util.HashMap;import java.util.Map;/** * @author Harrison * */public class FileTool { /** * Read talks-list.txt to map * * @return map, key:title; value:time; */ public static Map readTalksList2Map() { Map titleAndTime = new HashMap (); File file = new File("src/main/resources/talks-list.txt"); BufferedReader reader = null; try { reader = new BufferedReader(new FileReader(file)); String line = null; int numTime = 0; while ((line = reader.readLine()) != null) { int lastBlank = line.lastIndexOf(" "); String title = line.substring(0, lastBlank); String time = line.substring(lastBlank + 1); if (time.equals("lightning")) { numTime = 5; } else { // Remove "min" suffix numTime = Integer.parseInt(time.substring(0, time.length() - 3)); } titleAndTime.put(title, numTime); } reader.close(); } catch (IOException e) { e.printStackTrace(); } finally { if (reader != null) { try { reader.close(); } catch (IOException e1) { } } } return titleAndTime; }}
ConferenceSchedule 类负责生成具体会议的安排，实现如下：
package harrison.ConferenceTrackManagement;import java.util.ArrayList;import java.util.HashMap;import java.util.Iterator;import java.util.List;import java.util.Map;import java.util.Map.Entry;import java.util.Random;import java.util.Set;/** * Conference track management * * @author Harrison * */public class ConferenceSchedule { /** * Get a schedule instance */ public static void getSchedule() { Map titleAndTime = FileTool.readTalksList2Map(); Map titleAndTimeBak = new HashMap (titleAndTime); Map track1Forenoon = getTrackMap(titleAndTime, 180); Map track1Afternoon = getTrackMap(titleAndTime, 240); Map track2Forenoon = getTrackMap(titleAndTime, 180); Map track2Afternoon = getTrackMap(titleAndTime, 240); if (!titleAndTime.isEmpty()) { Map tempMap = new HashMap (titleAndTimeBak); while(!tempMap.isEmpty()){ tempMap = new HashMap (titleAndTimeBak); track1Forenoon = getTrackMap(tempMap, 180); track1Afternoon = getTrackMap(tempMap, 240); track2Forenoon = getTrackMap(tempMap, 180); track2Afternoon = getTrackMap(tempMap, 240); } } System.out.println("Track 1:"); printForenoonSchedule(track1Forenoon); printAfternoonSchedule(track1Afternoon); System.out.println("Track 2:"); printForenoonSchedule(track2Forenoon); printAfternoonSchedule(track2Afternoon); } /** * Print forenoon schedule * * @param trackMap */ public static void printForenoonSchedule(Map trackMap) { int sumTime = 0; int res = 0; String remainderStr = "00"; for (Entry entry : trackMap.entrySet()) { String title = entry.getKey(); int time = entry.getValue(); String timeStr = time == 5 ? "lightning" : time + ""; switch (res) { case 0: System.out.println("09:" + remainderStr + "AM " + title + " " + timeStr + "min"); break; case 1: System.out.println("10:" + remainderStr + "AM " + title + " " + timeStr + "min"); break; case 2: System.out.println("11:" + remainderStr + "AM " + title + " " + timeStr + "min"); break; default: break; } sumTime += time; res = sumTime / 60; int remainder = sumTime % 60; if (remainder / 10 == 0) { remainderStr = "0" + remainder; } else { remainderStr = remainder + ""; } } System.out.println("12:00PM Lunch"); } /** * Print afternoon schedule * * @param trackMap */ public static void printAfternoonSchedule(Map trackMap) { int sumTime = 0; int res = 0; String remainderStr = "00"; for (Entry entry : trackMap.entrySet()) { String title = entry.getKey(); int time = entry.getValue(); String timeStr = time == 5 ? "lightning" : time + ""; switch (res) { case 0: System.out.println("01:" + remainderStr + "PM " + title + " " + timeStr + "min"); break; case 1: System.out.println("02:" + remainderStr + "PM " + title + " " + timeStr + "min"); break; case 2: System.out.println("03:" + remainderStr + "PM " + title + " " + timeStr + "min"); break; case 3: System.out.println("04:" + remainderStr + "PM " + title + " " + timeStr + "min"); break; default: break; } sumTime += time; res = sumTime / 60; int remainder = sumTime % 60; if (remainder / 10 == 0) { remainderStr = "0" + remainder; } else { remainderStr = remainder + ""; } } System.out.println("05:00PM Networking Event"); } /** * Get each session track * * @param titleAndTime * @param totalMinute * @return */ public static Map getTrackMap(Map titleAndTime, int sessionMinute) { Map trackMap = new HashMap (); List titleList = new ArrayList (titleAndTime.keySet()); Random random = new Random(); int randomIndex = 0; String randomTitle = null; int time = 0; int sumTime = 0; while (sumTime < sessionMinute && titleList.size() > 0) { randomIndex = random.nextInt(titleList.size()); randomTitle = titleList.get(randomIndex); time = titleAndTime.get(randomTitle); sumTime += time; if (sumTime <= sessionMinute) { trackMap.put(randomTitle, time); } titleList.remove(randomTitle); } // Remove entry from titleAndTime which has already schedule Set trackMapKeySet = trackMap.keySet(); Iterator > it = titleAndTime.entrySet().iterator(); while (it.hasNext()) { if (trackMapKeySet.contains(it.next().getKey())) { it.remove(); } } return trackMap; }} 其中，getTrackMap 方法用于随机从所有萝卜中挑选出一组，其和不能大于所指定的大小，即坑的大小，由参数 sessionMinute 指定。getSchedule 方法通过调用 getTrackMap 依次生成 4 个坑中的数据，因为 getTrackMap 是随机挑选萝卜，可能出现所有萝卜并未全部入坑的情况，所以当分配失败时，在 getSchedule 中做了重试。如果分配成功，则调用 printForenoonSchedule 方法和 printAfternoonSchedule 方法格式化输出。
一个可能的解如下：
再次运行，产生另一个可能的解决，每次运行的结果并不一定相同，如下：
至此，实现完毕，但是这种做法并未得到面试官的认可，如有更优解，欢迎指教！