r**h
发帖数: 1288 | 1 有N个interval，每个有单独的startTime, endTime和cost
找一个subset，使得其中的interval互不相交，且cost最大
这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？ |
r*****e
发帖数: 792 | 2 好像去年f的onsite问过这题，当时花了
些时间想，最后用dp解的，不知道是不是最优解但面试官认可了我的解法。
不过那一轮只做了一道题，之前没见过这题。
【在 r**h 的大作中提到】
: 有N个interval，每个有单独的startTime, endTime和cost
: 找一个subset，使得其中的interval互不相交，且cost最大
: 这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？
|
r**h
发帖数: 1288 | 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解的，不知道是不是最优解但面试官认可了我的解法。
: 不过那一轮只做了一道题，之前没见过这题。
|
J****3
发帖数: 427 | 4 能说说为啥不能贪心吗？我怎么感觉和CLRS上例题好像啊 |
p*****2
发帖数: 21240 | 5 怎么感觉像是O(n^2)时间，O(n)空间的DP呀。 |
p*****2
发帖数: 21240 | 6
贪心怎么搞？话说一般interview碰到贪心的几率是蛮低的。
【在 J****3 的大作中提到】
: 能说说为啥不能贪心吗？我怎么感觉和CLRS上例题好像啊
|
h***i
发帖数: 1970 | 7 是,跟longest increasing sequence结构一样.
【在 p*****2 的大作中提到】
: 怎么感觉像是O(n^2)时间，O(n)空间的DP呀。
|
J****3
发帖数: 427 | |
J****3
发帖数: 427 | |
J****3
发帖数: 427 | 10 额 我二了 贪心给不出最大解吧。
【在 p*****2 的大作中提到】
:
: 贪心怎么搞？话说一般interview碰到贪心的几率是蛮低的。
|
r**h
发帖数: 1288 | 11 是哦，的确这样就可以了
感谢大牛们
【在 h***i 的大作中提到】
: 是,跟longest increasing sequence结构一样.
|
r**h
发帖数: 1288 | 12 是啊，而且不少贪心的题目好想不好写
【在 p*****2 的大作中提到】
:
: 贪心怎么搞？话说一般interview碰到贪心的几率是蛮低的。
|
x*********w
发帖数: 533 | 13
CLRS上greedy那章的课后题，不能用greedy,只可以DP
【在 r**h 的大作中提到】
: 有N个interval，每个有单独的startTime, endTime和cost
: 找一个subset，使得其中的interval互不相交，且cost最大
: 这题感觉不能用greedy呀。。难道只能枚举所有的子集吗？
|
j*****n
发帖数: 1545 | 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. |
