求助一道FB的高频题non-overlap jobs - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求助一道FB的高频题non-overlap jobs

求助一道FB的高频题non-overlap jobs# JobHunting - 待字闺中

y*82014-12-14 08:12

1 楼

先谢谢各位了！
题目是：Given a set of n jobs with [start time, end time, cost] find a
subset so that no 2 jobs overlap and the cost is maximum.
brute force 肯定是不行的了。我知道一个O(N^2)的解答，请问有更好的答案吗？谢谢
了！

d*n2014-12-14 08:12

2 楼

DP吧，先sort the jobs by end time, if the end time is the same, then by
start time.
Cost[i] = |- Cost[i-1] + JobCost[i] if job i doesn't overalap with previous
jobs
|- Max(Cost[i-1]， Cost[j]+ JobCost[i] where j is the closest job
which is not overlapping with job i

【在 y*******8 的大作中提到】

: 先谢谢各位了！
: 题目是：Given a set of n jobs with [start time, end time, cost] find a
: subset so that no 2 jobs overlap and the cost is maximum.
: brute force 肯定是不行的了。我知道一个O(N^2)的解答，请问有更好的答案吗？谢谢
: 了！

c*n2014-12-14 08:12

3 楼

http://cs.stackexchange.com/questions/11265/find-non-overlappin

y*82014-12-14 08:12

4 楼

谢谢二位了！
我也看到了这个post～只是没有看懂。。。。能解释一下下么？

【在 c******n 的大作中提到】

: http://cs.stackexchange.com/questions/11265/find-non-overlappin

y*82014-12-14 08:12

5 楼

恕我愚钝，请问为什么是按照end time sort呢？

previous
job

【在 d****n 的大作中提到】

: DP吧，先sort the jobs by end time, if the end time is the same, then by
: start time.
: Cost[i] = |- Cost[i-1] + JobCost[i] if job i doesn't overalap with previous
: jobs
: |- Max(Cost[i-1]， Cost[j]+ JobCost[i] where j is the closest job
: which is not overlapping with job i
:

j*g2014-12-14 08:12

6 楼

Mark

d*n2014-12-14 08:12

7 楼

按endtime的话，当你处理ith job时，可以通过binarysearch 很快找到最接近的job
which
is not overlapping with ith job。因为前面i-1个的endtime是递增的。

【在 y*******8 的大作中提到】

: 恕我愚钝，请问为什么是按照end time sort呢？
:
: previous
: job

y*82014-12-14 08:12

8 楼

学习了，谢谢！！！

job

【在 d****n 的大作中提到】

: 按endtime的话，当你处理ith job时，可以通过binarysearch 很快找到最接近的job
: which
: is not overlapping with ith job。因为前面i-1个的endtime是递增的。

h*c2014-12-14 08:12

9 楼

这个题如果time granualarity 比较coarse的话
比如
[3,5] -> ［３，４，５］
［１，７］－＞［１，２，３，４，５，６，７］
然后进hash map
有overlap就是weighted graph 的bfs
opinion

y*82014-12-14 08:12

10 楼

d*n2014-12-14 08:12

11 楼

c*n2014-12-14 08:12

12 楼

http://cs.stackexchange.com/questions/11265/find-non-overlappin

y*82014-12-14 08:12

13 楼

谢谢二位了！
我也看到了这个post～只是没有看懂。。。。能解释一下下么？

【在 c******n 的大作中提到】

: http://cs.stackexchange.com/questions/11265/find-non-overlappin

y*82014-12-14 08:12

14 楼

恕我愚钝，请问为什么是按照end time sort呢？

previous
job

【在 d****n 的大作中提到】

j*g2014-12-14 08:12

15 楼

Mark

d*n2014-12-14 08:12

16 楼

: 恕我愚钝，请问为什么是按照end time sort呢？
:
: previous
: job

y*82014-12-14 08:12

17 楼

学习了，谢谢！！！

job

【在 d****n 的大作中提到】

: 按endtime的话，当你处理ith job时，可以通过binarysearch 很快找到最接近的job
: which
: is not overlapping with ith job。因为前面i-1个的endtime是递增的。

h*c2014-12-14 08:12

18 楼

Q*w2014-12-14 08:12

19 楼

job
请教下如果end time有重复值，同一个end time对应不同的cost。。还能二分不？

【在 d****n 的大作中提到】

: 按endtime的话，当你处理ith job时，可以通过binarysearch 很快找到最接近的job
: which
: is not overlapping with ith job。因为前面i-1个的endtime是递增的。

m*t2014-12-14 08:12

20 楼

仔细看了一下文献，这个题目出出来挺坑人的。。。。
http://en.wikipedia.org/wiki/Interval_scheduling
算是 maximum weight independent set 的特殊情形，而且刚刚好有 polynomial time
的解法。。。我觉得没有相关 background 能想出来解法都不错了。。。。