Conference Track Management Problem Solution Java
前两天面试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 60min Overdoing it in Python 45min Lua for the Masses 30min Ruby Errors from Mismatched Gem Versions 45min Common Ruby Errors 45min Rails for Python Developers lightning Communicating Over Distance 60min Accounting-Driven Development 45min Woah 30min Sit Down and Write 30min Pair Programming vs Noise 45min Rails Magic 60min Ruby on Rails: Why We Should Move On 60min Clojure Ate Scala (on my project) 45min Programming in the Boondocks of Seattle 30min Ruby vs. Clojure for Back-End Development 30min Ruby on Rails Legacy App Maintenance 60min A World Without HackerNews 30min User Interface CSS in Rails Apps 30min Test output: Track 1: 09:00AM Writing Fast Tests Against Enterprise Rails 60min 10:00AM Overdoing it in Python 45min 10:45AM Lua for the Masses 30min 11:15AM Ruby Errors from Mismatched Gem Versions 45min 12:00PM Lunch 01:00PM Ruby on Rails: Why We Should Move On 60min 02:00PM Common Ruby Errors 45min 02:45PM Pair Programming vs Noise 45min 03:30PM Programming in the Boondocks of Seattle 30min 04:00PM Ruby vs. Clojure for Back-End Development 30min 04:30PM User Interface CSS in Rails Apps 30min 05:00PM Networking Event Track 2: 09:00AM Communicating Over Distance 60min 10:00AM Rails Magic 60min 11:00AM Woah 30min 11:30AM Sit Down and Write 30min 12:00PM Lunch 01:00PM Accounting-Driven Development 45min 01:45PM Clojure Ate Scala (on my project) 45min 02:30PM A World Without HackerNews 30min 03:00PM Ruby on Rails Legacy App Maintenance 60min 04:00PM Rails for Python Developers lightning 05: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<String, Integer> readTalksList2Map() { Map<String, Integer> titleAndTime = new HashMap<String, Integer>(); 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<String, Integer> titleAndTime = FileTool.readTalksList2Map(); Map<String, Integer> titleAndTimeBak = new HashMap<String, Integer>(titleAndTime); Map<String, Integer> track1Forenoon = getTrackMap(titleAndTime, 180); Map<String, Integer> track1Afternoon = getTrackMap(titleAndTime, 240); Map<String, Integer> track2Forenoon = getTrackMap(titleAndTime, 180); Map<String, Integer> track2Afternoon = getTrackMap(titleAndTime, 240); if (!titleAndTime.isEmpty()) { Map<String, Integer> tempMap = new HashMap<String, Integer>(titleAndTimeBak); while(!tempMap.isEmpty()){ tempMap = new HashMap<String, Integer>(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<String, Integer> trackMap) { int sumTime = 0; int res = 0; String remainderStr = "00"; for (Entry<String, Integer> 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<String, Integer> trackMap) { int sumTime = 0; int res = 0; String remainderStr = "00"; for (Entry<String, Integer> 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<String, Integer> getTrackMap(Map<String, Integer> titleAndTime, int sessionMinute) { Map<String, Integer> trackMap = new HashMap<String, Integer>(); List<String> titleList = new ArrayList<String>(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<String> trackMapKeySet = trackMap.keySet(); Iterator<Entry<String, Integer>> 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 方法格式化输出。
一个可能的解如下：
再次运行，产生另一个可能的解决，每次运行的结果并不一定相同，如下：
至此，实现完毕，但是这种做法并未得到面试官的认可，如有更优解，欢迎指教！
Conference Track Management Problem Solution Java
Source: https://www.cnblogs.com/HarrisonHao/p/6598557.html