h**o 发帖数: 548 | 1 1。 Given a vector of Nodes, each of which contain the start and end time of
a meeting, find the maximum number of meeting one would have to book for
the day.
2。 好像还见过一题是说每个node 包括 [start time, end time, weight].要求 不
overlap 的最大weight 和。
好像用greedy or DP 什么的。 什么思路? |
m****e 发帖数: 15 | 2 第一个按end time greedy, 第二个dp |
P****2 发帖数: 197 | 3 按START DATE排序,然后从后len-1=>0 DP
dp[i] = not pick: dp[i+1]
pick: weight[i]+ dp[j] (d[j]的j从i+1往后找第一个i.end > j.start,否
者为0,pick就是weight[i]) start是排序的可以二分找
return dp[0] |
m**********g 发帖数: 153 | 4 感觉按end time 排序更容易理解一些, 不过应该是个人习惯。
dp[i] = dp[i-1] //no pick
= weight[i-1] +dp[x]; x is the right most meeting whose end time is
smaller than the start time of meeting i.
//0 based index, bottom up
dp[0] = 0;
dp [1] = weight[0];
dp [2] = max(dp[1], weight[1] + dp[x])
..
dp[n] = max(dp[n-1], weight[n-1] + dp[x]);
return dp[n];
【在 P****2 的大作中提到】 : 按START DATE排序,然后从后len-1=>0 DP : dp[i] = not pick: dp[i+1] : pick: weight[i]+ dp[j] (d[j]的j从i+1往后找第一个i.end > j.start,否 : 者为0,pick就是weight[i]) start是排序的可以二分找 : return dp[0]
|
h**o 发帖数: 548 | 5 谢谢各位,没明白, 过两天再读读。
【在 m**********g 的大作中提到】 : 感觉按end time 排序更容易理解一些, 不过应该是个人习惯。 : dp[i] = dp[i-1] //no pick : = weight[i-1] +dp[x]; x is the right most meeting whose end time is : smaller than the start time of meeting i. : //0 based index, bottom up : dp[0] = 0; : dp [1] = weight[0]; : dp [2] = max(dp[1], weight[1] + dp[x]) : .. : dp[n] = max(dp[n-1], weight[n-1] + dp[x]);
|
s**x 发帖数: 7506 | |