l********a
发帖数: 5 | 1 “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky |
e*******8
发帖数: 94 | 2 dynamic programming? 就是weighted interval scheduling problem |
J****3
发帖数: 427 | |
J****3
发帖数: 427 | 4 记错了。那是贪心的。sorry 不过是DP求解吧
【在 J****3 的大作中提到】
: FA上动态规划的例题变体吧
|
h***u
发帖数: 9 | |
r*********n
发帖数: 4553 | 6 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. |
c********p
发帖数: 1969 | |
s*******n
发帖数: 305 | |
J****3
发帖数: 427 | 9 算法导论
【在 h***u 的大作中提到】
: 啥是 FA？
|
d******l
发帖数: 98 | 10 greedy algorithm on activity-selection |
|
|
J****3
发帖数: 427 | 11 greedy 求出来的不一定是最大吧？
【在 d******l 的大作中提到】
: greedy algorithm on activity-selection
|
t******i
发帖数: 483 | |
c********e
发帖数: 186 | 13 请问怎么定义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.
|
g*******i
发帖数: 110 | |
u*****o
发帖数: 1224 | |
p*****2
发帖数: 21240 | |
e*******8
发帖数: 94 | 17 不用２维吧，就按照完成时间排序然后一维dp就可以了 |
p*****2
发帖数: 21240 | 18
不好意思。刚才写错了。我的意思是n^2 dp
【在 e*******8 的大作中提到】
: 不用２维吧，就按照完成时间排序然后一维dp就可以了
|
e*******8
发帖数: 94 | 19 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp. |
p*****2
发帖数: 21240 | 20
大牛说说O(n)怎么搞呀？
【在 e*******8 的大作中提到】
: 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
: 前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
: 出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
|
|
|
p*****2
发帖数: 21240 | 21
算出每个interval最偏右的不与之重叠的那个interval的index
这个复杂度是多少呀？
【在 e*******8 的大作中提到】
: 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
: 前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
: 出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
|
e*******8
发帖数: 94 | 22 哎，大牛我可不敢当啊-_-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
: 这个复杂度是多少呀？
|
d****n
发帖数: 233 | 23 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).
|
J****3
发帖数: 427 | 24 光用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).
|
p*****3
发帖数: 488 | |
r*********n
发帖数: 4553 | 26
是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
发帖数: 520 | 27
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
发帖数: 520 | 28 总体来说时间复杂度应该是：
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
发帖数: 15480 | |
f********4
发帖数: 988 | 30 这第三次看到A家这道题了。。。Mark
【在 l********a 的大作中提到】
: “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
: 个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
: 没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
|
|
|
M*******u
发帖数: 51 | |
c********e
发帖数: 186 | 32 什么是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) );
|
c********e
发帖数: 186 | 33 同问，咋样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).
|
c**1
发帖数: 71 | 34 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 |
l********a
发帖数: 5 | 35 “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky |
e*******8
发帖数: 94 | 36 dynamic programming? 就是weighted interval scheduling problem |
J****3
发帖数: 427 | |
J****3
发帖数: 427 | 38 记错了。那是贪心的。sorry 不过是DP求解吧
【在 J****3 的大作中提到】
: FA上动态规划的例题变体吧
|
h***u
发帖数: 9 | |
r*********n
发帖数: 4553 | 40 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. |
|
|
c********p
发帖数: 1969 | |
s*******n
发帖数: 305 | |
J****3
发帖数: 427 | 43 算法导论
【在 h***u 的大作中提到】
: 啥是 FA？
|
d******l
发帖数: 98 | 44 greedy algorithm on activity-selection |
J****3
发帖数: 427 | 45 greedy 求出来的不一定是最大吧？
【在 d******l 的大作中提到】
: greedy algorithm on activity-selection
|
t******i
发帖数: 483 | |
c********e
发帖数: 186 | 47 请问怎么定义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.
|
g*******i
发帖数: 110 | |
u*****o
发帖数: 1224 | |
p*****2
发帖数: 21240 | |
|
|
e*******8
发帖数: 94 | 51 不用２维吧，就按照完成时间排序然后一维dp就可以了 |
p*****2
发帖数: 21240 | 52
不好意思。刚才写错了。我的意思是n^2 dp
【在 e*******8 的大作中提到】
: 不用２维吧，就按照完成时间排序然后一维dp就可以了
|
e*******8
发帖数: 94 | 53 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp. |
p*****2
发帖数: 21240 | 54
大牛说说O(n)怎么搞呀？
【在 e*******8 的大作中提到】
: 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
: 前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
: 出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
|
p*****2
发帖数: 21240 | 55
算出每个interval最偏右的不与之重叠的那个interval的index
这个复杂度是多少呀？
【在 e*******8 的大作中提到】
: 也用不了n^2啊, O(n)应该就可以了，当然空间复杂度也是O(n).
: 前提当然是所有的intervals已经按照完成时间排好序。然后可以做个preprocess，算
: 出每个interval最偏右的不与之重叠的那个interval的index. 然后再dp.
|
e*******8
发帖数: 94 | 56 哎，大牛我可不敢当啊-_-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
: 这个复杂度是多少呀？
|
d****n
发帖数: 233 | 57 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).
|
J****3
发帖数: 427 | 58 光用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).
|
p*****3
发帖数: 488 | |
r*********n
发帖数: 4553 | 60
是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
发帖数: 520 | 61
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
发帖数: 520 | 62 总体来说时间复杂度应该是：
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
发帖数: 15480 | |
f********4
发帖数: 988 | 64 这第三次看到A家这道题了。。。Mark
【在 l********a 的大作中提到】
: “有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一
: 个set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。”
: 没有思路，请大侠指点。感觉不少“时间安排”的题都很tricky
|
M*******u
发帖数: 51 | |
c********e
发帖数: 186 | 66 什么是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) );
|
c********e
发帖数: 186 | 67 同问，咋样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).
|
c**1
发帖数: 71 | 68 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 |
j******t
发帖数: 788 | 69 刚看到这个题目, 既然是亚麻常用提. 我来提供一个思路,看看可不可以, 这个思路绝
对能找到答案,但是不一定是复杂度最低
的.请发包子.
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
发帖数: 988 | |
|
|
D**********d
发帖数: 849 | 71 我想到的是 O(nlgn) 区间合并问题：
1. sort 所有端点 O(nlgn).
2. 扫描所有端点一次 O(n) 左正右负. |
j******t
发帖数: 788 | 72 no sort needed. bubble algorithm,
【在 D**********d 的大作中提到】
: 我想到的是 O(nlgn) 区间合并问题：
: 1. sort 所有端点 O(nlgn).
: 2. 扫描所有端点一次 O(n) 左正右负.
|
T******e
发帖数: 157 | 73 感觉像堆箱子的题
先根据开始时间排个序，这样扫的时候就会有规律些 |
d**********x
发帖数: 4083 | 74 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
|
w*******s
发帖数: 96 | |
w*******e
发帖数: 395 | 76 你这个就是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.
|
j******t
发帖数: 788 | 77 不完全是, 想想AUX在不短淘汰中, greedy algorithm 不可能保证GLOBAL OP.
而且我觉得还可以改进.一个思路是加PRE-process改进前面的方法, 其实这道题还可以
等价与最段路径问题.O(nLOGn)
每个RECORD是一个结点,相邻结点就是跟其interval不交接的其他RECORD,TOPOLOGY建立
好以后, 就成了一个GRAPH.以后就是经典解发了.
【在 w*******e 的大作中提到】
: 你这个就是brute force
:
: which
: records
: number,
|
w*******s
发帖数: 96 | 78 如果只是找个数， 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()];
} |
w*******s
发帖数: 96 | 79 更正： 排序应该安结束时间来。
struct mycomp{
bool operator() (const Interval &l, const Interval &r)
{
return l.endTime < r.endTime;
}
}myobj; |
j******t
发帖数: 788 | 80 没看明白,你假设要求的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;
|
|
|
j******t
发帖数: 788 | 81 你这个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;
|
n******h
发帖数: 5 | 82 unweighted用greedy，weighted用一维dp. |
s**x
发帖数: 7506 | 83 Dynamic programming - weighted activity selection algorithm.
O(nlogn)
http://www.cs.princeton.edu/~wayne/cs423/lectures/dynamic-progr |
z****e
发帖数: 54598 | |
j******t
发帖数: 788 | |
B*****g
发帖数: 34098 | 86 咣当
【在 j******t 的大作中提到】
: DP实际上就是BRUTAL FORCE对不对? 看这个.
: http://en.wikipedia.org/wiki/Dynamic_programming
|
