请教一题，关于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.
相关阅读
Re: why do you like computer programming?微软面试的小体会一个很全SAS Interview Q. List [ZT]谈谈我找工作的经验回忆一下面试时被问过的问题some experience to share (8) --- final words找工作心得-3：American DreamMy Jobhunting tips (maybe useful)我找工作的经验教训some experience to share (3) --- how to apply2004 Top 100 H1B Employer in New York State说说我的找工作的经验，CPA finance/accountingmyjobstory.com: 2004 Top 500 H1B Employer in USAsome experience to share (5) --- phone interviewJob hunting experience and more...找工作心得-续1：resume & cover letteryingp's job seeking experience (6)回报贴：我找工作的过程与经验一次找工作经历Sample interview questions