算法 邮箱里的一道题目, 有没有好的算法.

torvaldsdb · 2017年03月17日 · 最后由 torvaldsdb 回复于 2017年03月17日 · 8011 次阅读

关于排列组合的题目。昨晚用自己的方式已经解决。大家有没有好的算法探讨一下。

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 dont 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

我的大致思路是:

  • 上午 下午分别进行排列组合
  • 上午下午的组合拼接在一起
  • 把有数据重复的组合剔除掉 这个过程耗时很久。抛砖引玉

thought works 的笔试题?

这是个最优化问题,可以用 MILP 解决

设 Talk input i 的事件段是从 b_i 开始,时长为 L_i

Lunch 是个特殊事件,可以设 b_0 = 12:00, L_0 = 60min

对于 Networking event, 可以设 4:00 <= b_n <= 5:00

我们还可以引入一系列变量 x_ij, 如果 i 事件后如果紧接是 j 事件,那么 x_ij = 1, 否则 x_ij = 0

那么我们有:

\sigma_{i}{x_ij} = 1
\sigma_{j}{x_ij} = 1
x_ij (b_j - b_i - L_i) >= 0                 (*)
b_i >= 9:00
b_i + L_i <= b_n       (都在 networking event 前面)
binary x_ij

对于式子 (*), 它是非线性的,怎么办呢?

https://download.aimms.com/aimms/download/manuals/AIMMS3OM_IntegerProgrammingTricks.pdf 里有介绍怎么把它写成线性的

然后把这些约束都放到 solver 求解,如果出现 subtour (事件排成一个圈), 动态添加一个约束,直到最后得出一个解。

上面解决了一天内排日程的问题,如果要排很多天怎么办?可以把第二天的 Lunch 和 Networking 都 +24:00, 然后在两天之间塞进一个 Rest 事件解决。

另外一个办法 (其实更简单点...) 是按背包问题的方法做...

luikore 回复

应该原意就是考察背包问题的算法题目

teddyinfi 回复

是 面试题 但不是 thought works

需要 登录 后方可回复, 如果你还没有账号请 注册新账号