面试题之会议安排

最近工作太忙，自己输入不够所以最近没有输出什么有价值的技术文章。今天分享一个面试题的解法。现在基本上排在第一线的互联网公司面试时都会考算法题，而且题目不是单纯的算法而是描述一个场景，让面试者根据自己的知识选用自己认为合适的算法和面向对象思路解决场景中遇到的问题。

下面是一个朋友之前面试某公司时给出的题，自己尝试解决了一下并给出解题思路。

题目如下：

你正在准备一场大型的开发者会议，但是有一点点麻烦…… 这场会议为期两天，每天上午从九点开始，上午的会议安排到中午12点之前必须结束； 中午12点到下午1点之间是午餐时间，下午1点开始进行下午的会议，到下午5点前必须结束； 现在你有一个清单，上面写明了所有要安排的议题，和每个议题会占用的时间； 清单如下

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 清单中 lightning占用5分钟，其他议题都各自注明了占用时间 现在你要写一个程序把清单上的议题安排进四个时间段内。

预期的输出结果如下：

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

解题思路

• 场景中涉及两个事物，单个会议我们称之为Talk，所以在这个场景中一共有19个Talk对象，每个都有持续时长和名称。

• Talk需要被安排进Session中去，两天的上午下午一共有4个Session对象，每个session有总时长，上午的session为180分钟，下午的Session总时长为240分支。

• 接下来就是要把19个Talk对象，刚到4个Session的talk_list属性中。

• 安排会议前先把Talk对象们按照持续时长倒序排序。

• 循环Talk对象列表，将时长最长的Talk对象安排到剩余时间最多的Session对象中。

• 在每次循环中都要根据Session的剩余时长对Session对象们进行倒叙排列获取剩余时间最多的Session对象。

• 循环完成后19个Talk就被安排到4个Session中去了，然后按照要求的格式输出即可。

代码实现

Talk类：

# -*- coding=UTF-8 -*-
class Talk:
    """class represent a talk
    properties:
        words: list of talk name's word
        duration: number of minutes talk last
        name: talk's name
    """
    def __init__(self, line):
        """line: each line from input.txt that marked talk's name and duration
        """
        self.words = line.split(' ')
        duration = self.words[len(self.words) - 1].strip()
        # calculate the duration of this talk(unit of duration is minute)
        if duration == "lightning":
            self.duration = 5
        else:
            self.duration = int(duration[:-3])
        self.name = ' '.join(self.words)

Session类

# -*- coding=UTF-8 -*-
class Session:
    """ represent a session 
    properties:
        limit: minutes of session time limit
        talk_list: list of talk object
        used: number of minutes that has been used
        balance: the remained number of minutes in session object
    """
    def __init__(self, time_limit):
        self.limit = time_limit
        self.talk_list = [] # list storing talk objects
        self.used = 0 # minutes used
        self.balance = self.limit - self.used
    def add(self, talk):
        """Put talk in session's talk list
        """
        self.used += talk.duration
        self.balance = self.limit - self.used
        self.talk_list.append(talk)

main.py

# -*- coding=UTF-8 -*-
from Session import Session
from Talk import Talk
def build_talks_sesions():
    """Initialize all talks and sesssions objects
    """
    sessions = list(map(lambda x: Session(x), [180, 240, 180, 240]))
    talks = []
    with open('input.txt') as f:
        for line in f:
            talks.append(Talk(line.strip()))
    return sessions, talks
def arrange_conferences(talks, sessions):
    """arrange talks in sessions
    """
    talk = talks.pop(0)
    sessions.sort(key=lambda x: x.balance, reverse=True)
    sessions[0].add(talk)
    if len(talks) == 0:
        return sessions
    return arrange_conferences(talks, sessions)
def format_time_number(number):
    """Format time's number
    example: given 1 will return 01, given 10 will return 10
    """
    if int(number) < 10:
        return '0' + str(number)
    return str(number)
def print_schedule(sessions):
    """Print conference schedule
    """
    sessions.sort(key=lambda x: x.limit, reverse=False)
    am = [None, None]
    pm = [None, None]
    am[0], am[1], pm[0], pm[1] = sessions
    for i in range(2):
        print('Track' + str(i + 1))
        minutes = 9 * 60
        for talk in am[i].talk_list:
            h = format_time_number(minutes // 60)
            m = format_time_number(minutes % 60)
            print(h + ':' + m + 'AM ' + talk.name)
            minutes += talk.duration
        print('12:00PM Lunch')
        minutes = 1 * 60
        for talk in pm[i].talk_list:
            h = format_time_number(minutes // 60)
            m = format_time_number(minutes % 60)
            print(h + ':' + m + 'PM ' + talk.name)
            minutes += talk.duration
        print('05:00PM Networking Event')
def main():
    sessions, talks = build_talks_sesions()
    # sort talks by their duration
    talks.sort(key=lambda item: item.duration, reverse=True)
    # arrange talks in  these 4 sessions
    arranged_sessions = arrange_conferences(talks, sessions)
    # print schedule
    print_schedule(arranged_sessions)
if __name__ == "__main__":
    main()

很多公司答题时可选的语言里并没有PHP，并且Python的语法更富表达力一些，由于Python面向对象支持运算符重载，所以一些排序和运算可以直接作用在对象上，使用起来很方便所以就直接拿Python解了，感兴趣的可以自己拿PHP再解一遍，我自己其实写了一个PHP版本的，但是很多在python里现成的方法用PHP都需要自己编码实现代码实在是比Python版本的多了好多就不往文章里贴了。

点击阅读原文链接可以获取代码。