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 | |
