请教一题，关于interval# JobHunting - 待字闺中
r*h
1 楼
有N个interval，每个有单独的startTime, endTime和cost
找一个subset，使得其中的interval互不相交，且cost最大
这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？
找一个subset，使得其中的interval互不相交，且cost最大
这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？
r*e
2 楼
好像去年f的onsite问过这题，当时花了
些时间想，最后用dp解的，不知道是不是最优解但面试官认可了我的解法。
不过那一轮只做了一道题，之前没见过这题。
【在 r**h 的大作中提到】
: 有N个interval，每个有单独的startTime, endTime和cost
: 找一个subset，使得其中的interval互不相交，且cost最大
: 这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？
些时间想，最后用dp解的，不知道是不是最优解但面试官认可了我的解法。
不过那一轮只做了一道题，之前没见过这题。
【在 r**h 的大作中提到】
: 有N个interval，每个有单独的startTime, endTime和cost
: 找一个subset，使得其中的interval互不相交，且cost最大
: 这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？
r*h
3 楼
能说一下dp的思路吗？
我的想法是，先按照结束时间sort每个interval，然后使用
dp[i][j], start[i][j], end[i][j]分别存第i个到第j个interval的最大cost，最优解
的开始时间和结束时间
合并的时候先看两半dp[i][k]和dp[k+1][j]是否有intersection，如果没有的话就加起
来更新对应的开始和结束时间dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])
不知道这样是否可以呢
【在 r*****e 的大作中提到】
: 好像去年f的onsite问过这题，当时花了
: 些时间想，最后用dp解的，不知道是不是最优解但面试官认可了我的解法。
: 不过那一轮只做了一道题，之前没见过这题。
我的想法是，先按照结束时间sort每个interval，然后使用
dp[i][j], start[i][j], end[i][j]分别存第i个到第j个interval的最大cost，最优解
的开始时间和结束时间
合并的时候先看两半dp[i][k]和dp[k+1][j]是否有intersection，如果没有的话就加起
来更新对应的开始和结束时间dp[i][j] = max(dp[i][j], dp[i][k]+dp[k+1][j])
不知道这样是否可以呢
【在 r*****e 的大作中提到】
: 好像去年f的onsite问过这题，当时花了
: 些时间想，最后用dp解的，不知道是不是最优解但面试官认可了我的解法。
: 不过那一轮只做了一道题，之前没见过这题。
J*3
4 楼
能说说为啥不能贪心吗？我怎么感觉和CLRS上例题好像啊
p*2
5 楼
怎么感觉像是O(n^2)时间，O(n)空间的DP呀。
p*2
6 楼
贪心怎么搞？话说一般interview碰到贪心的几率是蛮低的。
【在 J****3 的大作中提到】
: 能说说为啥不能贪心吗？我怎么感觉和CLRS上例题好像啊
h*i
7 楼
是,跟longest increasing sequence结构一样.
【在 p*****2 的大作中提到】
: 怎么感觉像是O(n^2)时间，O(n)空间的DP呀。
【在 p*****2 的大作中提到】
: 怎么感觉像是O(n^2)时间，O(n)空间的DP呀。
J*3
8 楼
二爷讲讲？
J*3
9 楼
恩 LIS变体
J*3
10 楼
额 我二了 贪心给不出最大解吧。
【在 p*****2 的大作中提到】
:
: 贪心怎么搞？话说一般interview碰到贪心的几率是蛮低的。
【在 p*****2 的大作中提到】
:
: 贪心怎么搞？话说一般interview碰到贪心的几率是蛮低的。
r*h
11 楼
是哦，的确这样就可以了
感谢大牛们
【在 h***i 的大作中提到】
: 是,跟longest increasing sequence结构一样.
感谢大牛们
【在 h***i 的大作中提到】
: 是,跟longest increasing sequence结构一样.
r*h
12 楼
是啊，而且不少贪心的题目好想不好写
【在 p*****2 的大作中提到】
:
: 贪心怎么搞？话说一般interview碰到贪心的几率是蛮低的。
【在 p*****2 的大作中提到】
:
: 贪心怎么搞？话说一般interview碰到贪心的几率是蛮低的。
x*w
13 楼
CLRS上greedy那章的课后题，不能用greedy,只可以DP
【在 r**h 的大作中提到】
: 有N个interval，每个有单独的startTime, endTime和cost
: 找一个subset，使得其中的interval互不相交，且cost最大
: 这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？
j*n
14 楼
This problem is called 'weighted activity selection', you can only use DP to
solve it, greedy can only solve 'activity selection', or the un-weighted
version.
solve it, greedy can only solve 'activity selection', or the un-weighted
version.
相关阅读
请教一道面试题寻华盛顿附近EE学生兼职翻译（3.15日起一周） (转载)这周怎么回事？求助，帮老婆找工作(STATISTICS)问一个OPT和H1b的问题请问有大牛面试google的嵌入式软件工程师的吗？明早上面试了。今天都看不进去了float的格式化打印报个 Microsoft Offer (+个人心得经历)大家面M$的时候都知道是面哪个组吗？生物医药找Industry，techniques和publication哪个更重要？(转载) 50 Worst of the Worst (and Most Common) Job Interview Mistakes计算机猥琐男（又称码工）的春天终于到来了 (转载)发包子了未来两三年里美国就业市场供不应求？要调快一个小时么？JAVA/Flex Developer needed in a TOP IT company in silicon valley面试的时候和Programmer能谈什么呢？Western Digital is looking for Mechanical Engineer一个offer如何决定