求高清中文儿歌视频下载链接。# Parenting - 为人父母
l*a
1 楼
“有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
s*c
2 楼
记得以前7-11不管有没有加油站都算成加油站的，今天发现没加油站的这家算成
grocery了
7-ELEVEN STOREONLY 1,009 dollars and.90 Cents
Doing Business As 7-ELEVEN STOREONLY
Category Merchandise & Supplies - Groceries
grocery了
7-ELEVEN STOREONLY 1,009 dollars and.90 Cents
Doing Business As 7-ELEVEN STOREONLY
Category Merchandise & Supplies - Groceries
f*l
3 楼
小朋友喜欢中文歌。谢谢。
e*8
4 楼
dynamic programming? 就是weighted interval scheduling problem
m*2
5 楼
这个应该是7-Eleven自己弄的。
【在 s*****c 的大作中提到】
: 记得以前7-11不管有没有加油站都算成加油站的，今天发现没加油站的这家算成
: grocery了
: 7-ELEVEN STOREONLY 1,009 dollars and.90 Cents
:
: Doing Business As 7-ELEVEN STOREONLY
: Category Merchandise & Supplies - Groceries
【在 s*****c 的大作中提到】
: 记得以前7-11不管有没有加油站都算成加油站的，今天发现没加油站的这家算成
: grocery了
: 7-ELEVEN STOREONLY 1,009 dollars and.90 Cents
:
: Doing Business As 7-ELEVEN STOREONLY
: Category Merchandise & Supplies - Groceries
J*3
6 楼
FA上动态规划的例题变体吧
j*g
7 楼
你买的4.95 fee的是啥卡?
J*3
8 楼
记错了。那是贪心的。sorry 不过是DP求解吧
【在 J****3 的大作中提到】
: FA上动态规划的例题变体吧
【在 J****3 的大作中提到】
: FA上动态规划的例题变体吧
s*c
9 楼
灰香草
【在 j***g 的大作中提到】
: 你买的4.95 fee的是啥卡?
【在 j***g 的大作中提到】
: 你买的4.95 fee的是啥卡?
h*u
10 楼
啥是 FA？
a*r
11 楼
Merchant Category是商家按照Amex/Discover/Visa/Mastercard的规定设置的，不是商
家自己随便设的。
【在 m**2 的大作中提到】
: 这个应该是7-Eleven自己弄的。
家自己随便设的。
【在 m**2 的大作中提到】
: 这个应该是7-Eleven自己弄的。
r*n
12 楼
record = , assuming weight > 0
1. sort records w.r.t. start
2. make an array called aux, with the ith value being equal to the largest
weight sum of any subset of the first i records and containing the ith
record.
3. iterate through all records, and maintain an interval tree (when
encounter end, remove the corresponding interval from the tree). For the ith
record, use the tree to find the first non-overlapping interval j, and set
aux[i] = aux[j] + weight at i
4. iterate through aux and find the largest one.
1. sort records w.r.t. start
2. make an array called aux, with the ith value being equal to the largest
weight sum of any subset of the first i records and containing the ith
record.
3. iterate through all records, and maintain an interval tree (when
encounter end, remove the corresponding interval from the tree). For the ith
record, use the tree to find the first non-overlapping interval j, and set
aux[i] = aux[j] + weight at i
4. iterate through aux and find the largest one.
m*2
13 楼
我觉得商家有主动权吧，它们可能是要和credit card公司分摊cash back的花费的，所
以有主动权选category:
http://stirfrypoints.blogspot.com/2015/01/blog-post_17.html
【在 a****r 的大作中提到】
: Merchant Category是商家按照Amex/Discover/Visa/Mastercard的规定设置的，不是商
: 家自己随便设的。
以有主动权选category:
http://stirfrypoints.blogspot.com/2015/01/blog-post_17.html
【在 a****r 的大作中提到】
: Merchant Category是商家按照Amex/Discover/Visa/Mastercard的规定设置的，不是商
: 家自己随便设的。
c*p
14 楼
Mark
在哪看过。。。
在哪看过。。。
s*n
15 楼
Mark
J*3
16 楼
算法导论
【在 h***u 的大作中提到】
: 啥是 FA？
【在 h***u 的大作中提到】
: 啥是 FA？
d*l
17 楼
greedy algorithm on activity-selection
J*3
18 楼
greedy 求出来的不一定是最大吧？
【在 d******l 的大作中提到】
: greedy algorithm on activity-selection
【在 d******l 的大作中提到】
: greedy algorithm on activity-selection
t*i
19 楼
mark
c*e
20 楼
请问怎么定义the first-non overlapping interval, forward 还是 backward呢?
另外，我觉得the first one 不一定就是最优的那个。
不过我对interval tree 不熟，如果理解有误，大牛别介意啊！
naive一点的方法就是check 每一次前面的interval j，aux[i] = Max{aux[j]} +
weight at i, where i and j 不相交。当然这方法慢，要 O(n^2)
ith
set
【在 r*********n 的大作中提到】
: record =, assuming weight > 0
: 1. sort records w.r.t. start
: 2. make an array called aux, with the ith value being equal to the largest
: weight sum of any subset of the first i records and containing the ith
: record.
: 3. iterate through all records, and maintain an interval tree (when
: encounter end, remove the corresponding interval from the tree). For the ith
: record, use the tree to find the first non-overlapping interval j, and set
: aux[i] = aux[j] + weight at i
: 4. iterate through aux and find the largest one.
另外，我觉得the first one 不一定就是最优的那个。
不过我对interval tree 不熟，如果理解有误，大牛别介意啊！
naive一点的方法就是check 每一次前面的interval j，aux[i] = Max{aux[j]} +
weight at i, where i and j 不相交。当然这方法慢，要 O(n^2)
ith
set
【在 r*********n 的大作中提到】
: record =
: 1. sort records w.r.t. start
: 2. make an array called aux, with the ith value being equal to the largest
: weight sum of any subset of the first i records and containing the ith
: record.
: 3. iterate through all records, and maintain an interval tree (when
: encounter end, remove the corresponding interval from the tree). For the ith
: record, use the tree to find the first non-overlapping interval j, and set
: aux[i] = aux[j] + weight at i
: 4. iterate through aux and find the largest one.
g*i
21 楼
Mark
u*o
22 楼
这题说思路就行了还是必须写CODE啊。。。
p*2
23 楼
n^2 dp？
e*8
24 楼
不用２维吧，就按照完成时间排序然后一维dp就可以了
p*2
25 楼
不好意思。刚才写错了。我的意思是n^2 dp
【在 e*******8 的大作中提到】
: 不用２维吧，就按照完成时间排序然后一维dp就可以了
e*8
26 楼
也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
p*2
27 楼
大牛说说O(n)怎么搞呀？
【在 e*******8 的大作中提到】
: 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
: 前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
: 出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
p*2
28 楼
算出每个interval最偏右的不与之重叠的那个interval的index
这个复杂度是多少呀？
【在 e*******8 的大作中提到】
: 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
: 前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
: 出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
e*8
29 楼
哎，大牛我可不敢当啊-_-bbbb
我刚才想错了，那步preprocess也需要O(nlogn).
完整的算法大致是这样：
１.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
所以最后整个算法的时间复杂度是O(nlogn).
【在 p*****2 的大作中提到】
:
: 算出每个interval最偏右的不与之重叠的那个interval的index
: 这个复杂度是多少呀？
我刚才想错了，那步preprocess也需要O(nlogn).
完整的算法大致是这样：
１.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
所以最后整个算法的时间复杂度是O(nlogn).
【在 p*****2 的大作中提到】
:
: 算出每个interval最偏右的不与之重叠的那个interval的index
: 这个复杂度是多少呀？
d*n
30 楼
I'm wondering if the following works.
long maxSumNonOverlap(Record[] records) {
long[] sums = new long[records.length + 1];
long max = 0;
sums[0] = 0;
Arrays.sort(records, new Comparator() {
@Override
public int compare(Record o1, Record o2) {
int diff = o1.end - o2.end;
return diff == 0? o1.start - o2.start : diff;
}});
int i = 0;
for(; i < records.length; ++i)
{
if (i == 0)
sums[i + 1] = records[i].weight;
else {
int j = i - 1;
while(j >= 0 && records[i].start < records[j].end)
--j;
sums[i+1] = Math.max(sums[j + 1] + records[i].weight, sums[i
]);
}
}
max = sums[i];
Arrays.sort(records, new Comparator() {
@Override
public int compare(Record o1, Record o2) {
int diff =o1.start - o2.start;
return diff == 0? o1.end - o2.end: diff;
}});
i = records.length;
sums[i--] = 0;
for(; i >=0; --i)
{
if (i == records.length - 1)
sums[i] = records[i].weight;
else {
int j = i + 1;
while(j < records.length && records[i].end > records[j].start)
++j;
sums[i] = Math.max(sums[j] + records[i].weight, sums[i + 1]);
}
}
max = Math.max(max, sums[0]);
return max;
}
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
long maxSumNonOverlap(Record[] records) {
long[] sums = new long[records.length + 1];
long max = 0;
sums[0] = 0;
Arrays.sort(records, new Comparator
@Override
public int compare(Record o1, Record o2) {
int diff = o1.end - o2.end;
return diff == 0? o1.start - o2.start : diff;
}});
int i = 0;
for(; i < records.length; ++i)
{
if (i == 0)
sums[i + 1] = records[i].weight;
else {
int j = i - 1;
while(j >= 0 && records[i].start < records[j].end)
--j;
sums[i+1] = Math.max(sums[j + 1] + records[i].weight, sums[i
]);
}
}
max = sums[i];
Arrays.sort(records, new Comparator
@Override
public int compare(Record o1, Record o2) {
int diff =o1.start - o2.start;
return diff == 0? o1.end - o2.end: diff;
}});
i = records.length;
sums[i--] = 0;
for(; i >=0; --i)
{
if (i == records.length - 1)
sums[i] = records[i].weight;
else {
int j = i + 1;
while(j < records.length && records[i].end > records[j].start)
++j;
sums[i] = Math.max(sums[j] + records[i].weight, sums[i + 1]);
}
}
max = Math.max(max, sums[0]);
return max;
}
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
J*3
31 楼
光用binary search 判断不了是不是不重叠吧？
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
p*3
32 楼
n^2 dp worst case
r*n
33 楼
是forward，我又想了下，其实没有必要用interval treed，一般的tree，key是区间的
end时间，遇到一个新的区间就用该区间的start时间在tree里面去找其rank k，然后
aux[i] = aux[k-1] + weight[i]
其实思路和你的方法是一样的，只不过用tree rank找你的j只需要O(logN)time，总体
复杂都是O(NlogN)
【在 c********e 的大作中提到】
: 请问怎么定义the first-non overlapping interval, forward 还是 backward呢?
: 另外，我觉得the first one 不一定就是最优的那个。
: 不过我对interval tree 不熟，如果理解有误，大牛别介意啊！
: naive一点的方法就是check 每一次前面的interval j，aux[i] = Max{aux[j]} +
: weight at i, where i and j 不相交。当然这方法慢，要 O(n^2)
:
: ith
: set
f*b
34 楼
2爷问的果然精妙！！
我觉得应该时间是O（n),前提是要先sort一次start_time 再sort一次finish_time，空
间O(n).
写了一段代码计算这个：
我算的是某个interval最靠近其start time的interval的index, 这些index存在下面的
P数组里：
int[] ComputeP(Interval[] F,Interval[] S)
{
int i=0,j=0;
int[] P= new int[S.length];
while(i
if(F[i].finish_time<=S[j].start_time)
i++;
else if(F[i].finish_time>S[j].start_time)
{
P[S[j].f_index]=i-1;
j++;
}
}
return P;
}
【在 p*****2 的大作中提到】
:
: 算出每个interval最偏右的不与之重叠的那个interval的index
: 这个复杂度是多少呀？
f*b
35 楼
总体来说时间复杂度应该是：
Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
memorized了？？就是2爷说的cache
int CalMax(Interval[] inputs,int end, int[] P)
{
if(end<0)
return 0;
return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
CalMax(inputs,--end,P) );
}
Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
memorized了？？就是2爷说的cache
int CalMax(Interval[] inputs,int end, int[] P)
{
if(end<0)
return 0;
return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
CalMax(inputs,--end,P) );
}
a*m
36 楼
感觉不可能nlgn吧，除非贪心可以满足需要。
f*4
37 楼
这第三次看到A家这道题了。。。Mark
【在 l********a 的大作中提到】
: “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
: 个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
: 没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
【在 l********a 的大作中提到】
: “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
: 个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
: 没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
M*u
38 楼
同求怎么有O(n)的解法
c*e
39 楼
什么是S[j].f_index呢？
怎么定义最靠近其start time的interval？最靠近根据位置，end time？
给个例子行不，牛哥？
【在 f*******b 的大作中提到】
: 总体来说时间复杂度应该是：
: Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
: DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
: memorized了？？就是2爷说的cache
: int CalMax(Interval[] inputs,int end, int[] P)
: {
: if(end<0)
: return 0;
: return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
: CalMax(inputs,--end,P) );
怎么定义最靠近其start time的interval？最靠近根据位置，end time？
给个例子行不，牛哥？
【在 f*******b 的大作中提到】
: 总体来说时间复杂度应该是：
: Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
: DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
: memorized了？？就是2爷说的cache
: int CalMax(Interval[] inputs,int end, int[] P)
: {
: if(end<0)
: return 0;
: return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
: CalMax(inputs,--end,P) );
c*e
40 楼
同问，咋样binary searchne， end不是sorted啊？
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
c*1
41 楼
sort all start / end points (O(nlogn), then the following is O(n)
sum = 0;
scan from first point
if it is a start point
this_interval.potential = sum + this.value;
else if this_interval.potential > sum
sum = this_interval.potential
return sum
sum = 0;
scan from first point
if it is a start point
this_interval.potential = sum + this.value;
else if this_interval.potential > sum
sum = this_interval.potential
return sum
l*a
42 楼
“有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
e*8
43 楼
dynamic programming? 就是weighted interval scheduling problem
J*3
44 楼
FA上动态规划的例题变体吧
J*3
45 楼
记错了。那是贪心的。sorry 不过是DP求解吧
【在 J****3 的大作中提到】
: FA上动态规划的例题变体吧
【在 J****3 的大作中提到】
: FA上动态规划的例题变体吧
h*u
46 楼
啥是 FA？
r*n
47 楼
record = , assuming weight > 0
1. sort records w.r.t. start
2. make an array called aux, with the ith value being equal to the largest
weight sum of any subset of the first i records and containing the ith
record.
3. iterate through all records, and maintain an interval tree (when
encounter end, remove the corresponding interval from the tree). For the ith
record, use the tree to find the first non-overlapping interval j, and set
aux[i] = aux[j] + weight at i
4. iterate through aux and find the largest one.
1. sort records w.r.t. start
2. make an array called aux, with the ith value being equal to the largest
weight sum of any subset of the first i records and containing the ith
record.
3. iterate through all records, and maintain an interval tree (when
encounter end, remove the corresponding interval from the tree). For the ith
record, use the tree to find the first non-overlapping interval j, and set
aux[i] = aux[j] + weight at i
4. iterate through aux and find the largest one.
c*p
48 楼
Mark
在哪看过。。。
在哪看过。。。
s*n
49 楼
Mark
J*3
50 楼
算法导论
【在 h***u 的大作中提到】
: 啥是 FA？
【在 h***u 的大作中提到】
: 啥是 FA？
d*l
51 楼
greedy algorithm on activity-selection
J*3
52 楼
greedy 求出来的不一定是最大吧？
【在 d******l 的大作中提到】
: greedy algorithm on activity-selection
【在 d******l 的大作中提到】
: greedy algorithm on activity-selection
t*i
53 楼
mark
c*e
54 楼
请问怎么定义the first-non overlapping interval, forward 还是 backward呢?
另外，我觉得the first one 不一定就是最优的那个。
不过我对interval tree 不熟，如果理解有误，大牛别介意啊！
naive一点的方法就是check 每一次前面的interval j，aux[i] = Max{aux[j]} +
weight at i, where i and j 不相交。当然这方法慢，要 O(n^2)
ith
set
【在 r*********n 的大作中提到】
: record =, assuming weight > 0
: 1. sort records w.r.t. start
: 2. make an array called aux, with the ith value being equal to the largest
: weight sum of any subset of the first i records and containing the ith
: record.
: 3. iterate through all records, and maintain an interval tree (when
: encounter end, remove the corresponding interval from the tree). For the ith
: record, use the tree to find the first non-overlapping interval j, and set
: aux[i] = aux[j] + weight at i
: 4. iterate through aux and find the largest one.
另外，我觉得the first one 不一定就是最优的那个。
不过我对interval tree 不熟，如果理解有误，大牛别介意啊！
naive一点的方法就是check 每一次前面的interval j，aux[i] = Max{aux[j]} +
weight at i, where i and j 不相交。当然这方法慢，要 O(n^2)
ith
set
【在 r*********n 的大作中提到】
: record =
: 1. sort records w.r.t. start
: 2. make an array called aux, with the ith value being equal to the largest
: weight sum of any subset of the first i records and containing the ith
: record.
: 3. iterate through all records, and maintain an interval tree (when
: encounter end, remove the corresponding interval from the tree). For the ith
: record, use the tree to find the first non-overlapping interval j, and set
: aux[i] = aux[j] + weight at i
: 4. iterate through aux and find the largest one.
g*i
55 楼
Mark
u*o
56 楼
这题说思路就行了还是必须写CODE啊。。。
p*2
57 楼
n^2 dp？
e*8
58 楼
不用２维吧，就按照完成时间排序然后一维dp就可以了
p*2
59 楼
不好意思。刚才写错了。我的意思是n^2 dp
【在 e*******8 的大作中提到】
: 不用２维吧，就按照完成时间排序然后一维dp就可以了
e*8
60 楼
也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
p*2
61 楼
大牛说说O(n)怎么搞呀？
【在 e*******8 的大作中提到】
: 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
: 前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
: 出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
p*2
62 楼
算出每个interval最偏右的不与之重叠的那个interval的index
这个复杂度是多少呀？
【在 e*******8 的大作中提到】
: 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
: 前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
: 出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
e*8
63 楼
哎，大牛我可不敢当啊-_-bbbb
我刚才想错了，那步preprocess也需要O(nlogn).
完整的算法大致是这样：
１.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
所以最后整个算法的时间复杂度是O(nlogn).
【在 p*****2 的大作中提到】
:
: 算出每个interval最偏右的不与之重叠的那个interval的index
: 这个复杂度是多少呀？
我刚才想错了，那步preprocess也需要O(nlogn).
完整的算法大致是这样：
１.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
所以最后整个算法的时间复杂度是O(nlogn).
【在 p*****2 的大作中提到】
:
: 算出每个interval最偏右的不与之重叠的那个interval的index
: 这个复杂度是多少呀？
d*n
64 楼
I'm wondering if the following works.
long maxSumNonOverlap(Record[] records) {
long[] sums = new long[records.length + 1];
long max = 0;
sums[0] = 0;
Arrays.sort(records, new Comparator() {
@Override
public int compare(Record o1, Record o2) {
int diff = o1.end - o2.end;
return diff == 0? o1.start - o2.start : diff;
}});
int i = 0;
for(; i < records.length; ++i)
{
if (i == 0)
sums[i + 1] = records[i].weight;
else {
int j = i - 1;
while(j >= 0 && records[i].start < records[j].end)
--j;
sums[i+1] = Math.max(sums[j + 1] + records[i].weight, sums[i
]);
}
}
max = sums[i];
Arrays.sort(records, new Comparator() {
@Override
public int compare(Record o1, Record o2) {
int diff =o1.start - o2.start;
return diff == 0? o1.end - o2.end: diff;
}});
i = records.length;
sums[i--] = 0;
for(; i >=0; --i)
{
if (i == records.length - 1)
sums[i] = records[i].weight;
else {
int j = i + 1;
while(j < records.length && records[i].end > records[j].start)
++j;
sums[i] = Math.max(sums[j] + records[i].weight, sums[i + 1]);
}
}
max = Math.max(max, sums[0]);
return max;
}
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
long maxSumNonOverlap(Record[] records) {
long[] sums = new long[records.length + 1];
long max = 0;
sums[0] = 0;
Arrays.sort(records, new Comparator
@Override
public int compare(Record o1, Record o2) {
int diff = o1.end - o2.end;
return diff == 0? o1.start - o2.start : diff;
}});
int i = 0;
for(; i < records.length; ++i)
{
if (i == 0)
sums[i + 1] = records[i].weight;
else {
int j = i - 1;
while(j >= 0 && records[i].start < records[j].end)
--j;
sums[i+1] = Math.max(sums[j + 1] + records[i].weight, sums[i
]);
}
}
max = sums[i];
Arrays.sort(records, new Comparator
@Override
public int compare(Record o1, Record o2) {
int diff =o1.start - o2.start;
return diff == 0? o1.end - o2.end: diff;
}});
i = records.length;
sums[i--] = 0;
for(; i >=0; --i)
{
if (i == records.length - 1)
sums[i] = records[i].weight;
else {
int j = i + 1;
while(j < records.length && records[i].end > records[j].start)
++j;
sums[i] = Math.max(sums[j] + records[i].weight, sums[i + 1]);
}
}
max = Math.max(max, sums[0]);
return max;
}
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
J*3
65 楼
光用binary search 判断不了是不是不重叠吧？
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
p*3
66 楼
n^2 dp worst case
r*n
67 楼
是forward，我又想了下，其实没有必要用interval treed，一般的tree，key是区间的
end时间，遇到一个新的区间就用该区间的start时间在tree里面去找其rank k，然后
aux[i] = aux[k-1] + weight[i]
其实思路和你的方法是一样的，只不过用tree rank找你的j只需要O(logN)time，总体
复杂都是O(NlogN)
【在 c********e 的大作中提到】
: 请问怎么定义the first-non overlapping interval, forward 还是 backward呢?
: 另外，我觉得the first one 不一定就是最优的那个。
: 不过我对interval tree 不熟，如果理解有误，大牛别介意啊！
: naive一点的方法就是check 每一次前面的interval j，aux[i] = Max{aux[j]} +
: weight at i, where i and j 不相交。当然这方法慢，要 O(n^2)
:
: ith
: set
f*b
68 楼
2爷问的果然精妙！！
我觉得应该时间是O（n),前提是要先sort一次start_time 再sort一次finish_time，空
间O(n).
写了一段代码计算这个：
我算的是某个interval最靠近其start time的interval的index, 这些index存在下面的
P数组里：
int[] ComputeP(Interval[] F,Interval[] S)
{
int i=0,j=0;
int[] P= new int[S.length];
while(i
if(F[i].finish_time<=S[j].start_time)
i++;
else if(F[i].finish_time>S[j].start_time)
{
P[S[j].f_index]=i-1;
j++;
}
}
return P;
}
【在 p*****2 的大作中提到】
:
: 算出每个interval最偏右的不与之重叠的那个interval的index
: 这个复杂度是多少呀？
f*b
69 楼
总体来说时间复杂度应该是：
Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
memorized了？？就是2爷说的cache
int CalMax(Interval[] inputs,int end, int[] P)
{
if(end<0)
return 0;
return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
CalMax(inputs,--end,P) );
}
Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
memorized了？？就是2爷说的cache
int CalMax(Interval[] inputs,int end, int[] P)
{
if(end<0)
return 0;
return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
CalMax(inputs,--end,P) );
}
a*m
70 楼
感觉不可能nlgn吧，除非贪心可以满足需要。
f*4
71 楼
这第三次看到A家这道题了。。。Mark
【在 l********a 的大作中提到】
: “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
: 个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
: 没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
【在 l********a 的大作中提到】
: “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
: 个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
: 没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
M*u
72 楼
同求怎么有O(n)的解法
c*e
73 楼
什么是S[j].f_index呢？
怎么定义最靠近其start time的interval？最靠近根据位置，end time？
给个例子行不，牛哥？
【在 f*******b 的大作中提到】
: 总体来说时间复杂度应该是：
: Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
: DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
: memorized了？？就是2爷说的cache
: int CalMax(Interval[] inputs,int end, int[] P)
: {
: if(end<0)
: return 0;
: return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
: CalMax(inputs,--end,P) );
怎么定义最靠近其start time的interval？最靠近根据位置，end time？
给个例子行不，牛哥？
【在 f*******b 的大作中提到】
: 总体来说时间复杂度应该是：
: Sort:O（nlogn)+找P:O(n)+DP:O(n)=O(nlogn)
: DP代码：用recursive做的bottom down，虽然是直接用数组的值，但不知道这个算不算
: memorized了？？就是2爷说的cache
: int CalMax(Interval[] inputs,int end, int[] P)
: {
: if(end<0)
: return 0;
: return Math.max(CalMax(inputs,P[end],P)+inputs[end].weight,
: CalMax(inputs,--end,P) );
c*e
74 楼
同问，咋样binary searchne， end不是sorted啊？
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
space.
＝n
【在 e*******8 的大作中提到】
: 哎，大牛我可不敢当啊-_-bbbb
: 我刚才想错了，那步preprocess也需要O(nlogn).
: 完整的算法大致是这样：
: １.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
: ２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
: binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
: 3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
: ，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
: 所以最后整个算法的时间复杂度是O(nlogn).
c*1
75 楼
sort all start / end points (O(nlogn), then the following is O(n)
sum = 0;
scan from first point
if it is a start point
this_interval.potential = sum + this.value;
else if this_interval.potential > sum
sum = this_interval.potential
return sum
sum = 0;
scan from first point
if it is a start point
this_interval.potential = sum + this.value;
else if this_interval.potential > sum
sum = this_interval.potential
return sum
j*t
76 楼
刚看到这个题目, 既然是亚麻常用提. 我来提供一个思路,看看可不可以, 这个思路绝
对能找到答案,但是不一定是复杂度最低
的.请发包子.
Let assume we have n records, and the required record number if p.
1, couple the record into sets of another structure. Lets call it aux, which
include any coupled records. Namely any ith and jth record build a aux,
totaly we can have n*(n-1) aux.
2, calculate the new weight of the each aux, if the interval of its records
has overlaps, the weight of that aux will be set as some crazy small number,
which indicts this aux is not feasible choice.
3, remove all the aux that have crazy small weight
4, build a new sets by coupling the input records and the aux we just sorted
.lets say we have q aux left, the new set of aux will be q*(n-1).
5, recursive search and sort. until the record number of aux reach the
required set number.
6, find the maximum weight from all the remaining aux structures with the
new calculated weights.
Good luck
对能找到答案,但是不一定是复杂度最低
的.请发包子.
Let assume we have n records, and the required record number if p.
1, couple the record into sets of another structure. Lets call it aux, which
include any coupled records. Namely any ith and jth record build a aux,
totaly we can have n*(n-1) aux.
2, calculate the new weight of the each aux, if the interval of its records
has overlaps, the weight of that aux will be set as some crazy small number,
which indicts this aux is not feasible choice.
3, remove all the aux that have crazy small weight
4, build a new sets by coupling the input records and the aux we just sorted
.lets say we have q aux left, the new set of aux will be q*(n-1).
5, recursive search and sort. until the record number of aux reach the
required set number.
6, find the maximum weight from all the remaining aux structures with the
new calculated weights.
Good luck
f*4
77 楼
这个题．．昨天看到一个报G家面经的还报过
D*d
78 楼
我想到的是 O(nlgn) 区间合并问题：
1. sort 所有端点 O(nlgn).
2. 扫描所有端点一次 O(n) 左正右负.
1. sort 所有端点 O(nlgn).
2. 扫描所有端点一次 O(n) 左正右负.
j*t
79 楼
no sort needed. bubble algorithm,
【在 D**********d 的大作中提到】
: 我想到的是 O(nlgn) 区间合并问题：
: 1. sort 所有端点 O(nlgn).
: 2. 扫描所有端点一次 O(n) 左正右负.
【在 D**********d 的大作中提到】
: 我想到的是 O(nlgn) 区间合并问题：
: 1. sort 所有端点 O(nlgn).
: 2. 扫描所有端点一次 O(n) 左正右负.
T*e
80 楼
感觉像堆箱子的题
先根据开始时间排个序，这样扫的时候就会有规律些
先根据开始时间排个序，这样扫的时候就会有规律些
d*x
81 楼
Given T1, if I(T1) is the interval with largest ending time before T1:
opt(T1) = max{opt(I(T1).start) + I(T1).weight, opt(T1 - 1)}
in case of multiple intervals have same ending time, we just need to loop
through them and calculate the opt value.
【在 l********a 的大作中提到】
: “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
: 个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
: 没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
opt(T1) = max{opt(I(T1).start) + I(T1).weight, opt(T1 - 1)}
in case of multiple intervals have same ending time, we just need to loop
through them and calculate the opt value.
【在 l********a 的大作中提到】
: “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
: 个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
: 没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
w*s
82 楼
Mark
w*e
83 楼
你这个就是brute force
which
records
number,
【在 j******t 的大作中提到】
: 刚看到这个题目, 既然是亚麻常用提. 我来提供一个思路,看看可不可以, 这个思路绝
: 对能找到答案,但是不一定是复杂度最低
: 的.请发包子.
: Let assume we have n records, and the required record number if p.
: 1, couple the record into sets of another structure. Lets call it aux, which
: include any coupled records. Namely any ith and jth record build a aux,
: totaly we can have n*(n-1) aux.
: 2, calculate the new weight of the each aux, if the interval of its records
: has overlaps, the weight of that aux will be set as some crazy small number,
: which indicts this aux is not feasible choice.
which
records
number,
【在 j******t 的大作中提到】
: 刚看到这个题目, 既然是亚麻常用提. 我来提供一个思路,看看可不可以, 这个思路绝
: 对能找到答案,但是不一定是复杂度最低
: 的.请发包子.
: Let assume we have n records, and the required record number if p.
: 1, couple the record into sets of another structure. Lets call it aux, which
: include any coupled records. Namely any ith and jth record build a aux,
: totaly we can have n*(n-1) aux.
: 2, calculate the new weight of the each aux, if the interval of its records
: has overlaps, the weight of that aux will be set as some crazy small number,
: which indicts this aux is not feasible choice.
j*t
84 楼
不完全是, 想想AUX在不短淘汰中, greedy algorithm 不可能保证GLOBAL OP.
而且我觉得还可以改进.一个思路是加PRE-process改进前面的方法, 其实这道题还可以
等价与最段路径问题.O(nLOGn)
每个RECORD是一个结点,相邻结点就是跟其interval不交接的其他RECORD,TOPOLOGY建立
好以后, 就成了一个GRAPH.以后就是经典解发了.
【在 w*******e 的大作中提到】
: 你这个就是brute force
:
: which
: records
: number,
而且我觉得还可以改进.一个思路是加PRE-process改进前面的方法, 其实这道题还可以
等价与最段路径问题.O(nLOGn)
每个RECORD是一个结点,相邻结点就是跟其interval不交接的其他RECORD,TOPOLOGY建立
好以后, 就成了一个GRAPH.以后就是经典解发了.
【在 w*******e 的大作中提到】
: 你这个就是brute force
:
: which
: records
: number,
w*s
85 楼
如果只是找个数， sort + dp .
struct Interval{
int startTime;
int endTime;
int w;
}
struct mycomp{
bool operator() (const Interval &l, const Interval &r)
{
return l.startTime < r.startTime;
}
}myobj;
int weightedInterval(vector &V)
{
// O(nlogn)
sort(v.begin(), v.end(), myobj);
// P[i]: the largest Index on the left who is not overlapped with V[i]
// O(n2)
vector P(V.size());
P[0] = 0;
for (int i=1; i
P[i] = 0 //by default
for (int j=i-1; j>=0 ;j--)
{
if (V[j].endTime < V[i].startTime){
P[i] = j;
break;
}
}
}
// O(n)
// Now DP
vector DP(V.size() + 1);
DP[0] = 0;
for (int i=1; i<=V.size(); i++ )
{
DP[i] = max(DP[i-1], DP[P[i]]+V[i].w);
}
return DP[V.size()];
}
struct Interval{
int startTime;
int endTime;
int w;
}
struct mycomp{
bool operator() (const Interval &l, const Interval &r)
{
return l.startTime < r.startTime;
}
}myobj;
int weightedInterval(vector
{
// O(nlogn)
sort(v.begin(), v.end(), myobj);
// P[i]: the largest Index on the left who is not overlapped with V[i]
// O(n2)
vector
P[0] = 0;
for (int i=1; i
P[i] = 0 //by default
for (int j=i-1; j>=0 ;j--)
{
if (V[j].endTime < V[i].startTime){
P[i] = j;
break;
}
}
}
// O(n)
// Now DP
vector
DP[0] = 0;
for (int i=1; i<=V.size(); i++ )
{
DP[i] = max(DP[i-1], DP[P[i]]+V[i].w);
}
return DP[V.size()];
}
w*s
86 楼
更正： 排序应该安结束时间来。
struct mycomp{
bool operator() (const Interval &l, const Interval &r)
{
return l.endTime < r.endTime;
}
}myobj;
struct mycomp{
bool operator() (const Interval &l, const Interval &r)
{
return l.endTime < r.endTime;
}
}myobj;
j*t
87 楼
没看明白,你假设要求的SET里面只有两个RECORDS, 是吗?
既然是SET, 这个SET里面可以有制定的多个RECORD.问题要复杂的多吧?
【在 w*******s 的大作中提到】
: 如果只是找个数， sort + dp .
: struct Interval{
: int startTime;
: int endTime;
: int w;
: }
: struct mycomp{
: bool operator() (const Interval &l, const Interval &r)
: {
: return l.startTime < r.startTime;
既然是SET, 这个SET里面可以有制定的多个RECORD.问题要复杂的多吧?
【在 w*******s 的大作中提到】
: 如果只是找个数， sort + dp .
: struct Interval{
: int startTime;
: int endTime;
: int w;
: }
: struct mycomp{
: bool operator() (const Interval &l, const Interval &r)
: {
: return l.startTime < r.startTime;
j*t
88 楼
你这个FUNCTOR已经过时了.check lambda,anonymous function for VC++11
【在 w*******s 的大作中提到】
: 更正： 排序应该安结束时间来。
: struct mycomp{
: bool operator() (const Interval &l, const Interval &r)
: {
: return l.endTime < r.endTime;
: }
: }myobj;
【在 w*******s 的大作中提到】
: 更正： 排序应该安结束时间来。
: struct mycomp{
: bool operator() (const Interval &l, const Interval &r)
: {
: return l.endTime < r.endTime;
: }
: }myobj;
n*h
89 楼
unweighted用greedy，weighted用一维dp.
s*x
90 楼
Dynamic programming - weighted activity selection algorithm.
O(nlogn)
http://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-progr
O(nlogn)
http://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-progr
z*e
91 楼
dp吧
时间复杂度主要是在sort上
时间复杂度主要是在sort上
j*t
92 楼
DP实际上就是BRUTAL FORCE对不对? 看这个.
http://en.wikipedia.org/wiki/Dynamic_programming
http://en.wikipedia.org/wiki/Dynamic_programming
B*g
93 楼
咣当
【在 j******t 的大作中提到】
: DP实际上就是BRUTAL FORCE对不对? 看这个.
: http://en.wikipedia.org/wiki/Dynamic_programming
【在 j******t 的大作中提到】
: DP实际上就是BRUTAL FORCE对不对? 看这个.
: http://en.wikipedia.org/wiki/Dynamic_programming
相关阅读