电视上就职典礼了，我们也来庆祝吧 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Parenting - 为人父母

电视上就职典礼了，我们也来庆祝吧 (转载)

电视上就职典礼了，我们也来庆祝吧 (转载)# Parenting - 为人父母

y*n2017-01-19 08:01

1 楼

有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一个
set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。
给个思路就行了。。

f*n2017-01-19 08:01

2 楼

【以下文字转载自 USANews 讨论区】
发信人: fishingarden (Edward Blum门下老王), 信区: USANews
标题: 电视上就职典礼了，我们也来庆祝吧
发信站: BBS 未名空间站 (Thu Jan 19 17:14:34 2017, 美东)
看看我们的视频吧！
http://m.youtube.com/watch?v=NZahDG8b_gw
老王再次跪地感激七十几位兄弟姐妹。

s*s2017-01-19 08:01

3 楼

先排序
在排序后的数组里定义m[i]表示以i结尾的最大权重
m[i] = max(m[k] + weight[k]) 其中k的结束时间小于i的开始时间
时间复杂度O(N^2)

l*s2017-01-19 08:01

4 楼

礼炮。。。
散花。。。。

y*n2017-01-19 08:01

5 楼

DP ?

【在 s*********s 的大作中提到】

: 先排序
: 在排序后的数组里定义m[i]表示以i结尾的最大权重
: m[i] = max(m[k] + weight[k]) 其中k的结束时间小于i的开始时间
: 时间复杂度O(N^2)

t*d2017-01-19 08:01

6 楼

赞老王，余额捐了反AA组织

r*k2017-01-19 08:01

7 楼

怎么看着那么像LIS问题
不过好像没办法向LIS那样继续优化到 O(NlogN)了

【在 s*********s 的大作中提到】

: 先排序
: 在排序后的数组里定义m[i]表示以i结尾的最大权重
: m[i] = max(m[k] + weight[k]) 其中k的结束时间小于i的开始时间
: 时间复杂度O(N^2)

l*s2017-01-19 08:01

8 楼

不知道啥时候募捐的
错过了

r*k2017-01-19 08:01

9 楼

好像可以进一步优化，类似LIS优化成O(NlgN)
之前的所有record的upper bound是排序了的。
用i+1个record的lower bound去upper bound里二分查找，可以找到不想交的最大index
，然后低于这个index的就不用比了。高于这个index的，由于相交了，也不用比了。
这需要另外一个数组X记录低于i的最大值。因为M[i]是以i结尾的最大值，并不是小于
等于i的最大值。
不过这么看，M都没有记录的必要了。。。
因为高于i的那些record，也就是和i+1有交集的，也有可能是最大值。
所以M[i+1]可以通过二分查找迅速算出，但X[i+1]必须用M[i+1]和X[i]比较之后算出

【在 r*******k 的大作中提到】

: 怎么看着那么像LIS问题
: 不过好像没办法向LIS那样继续优化到 O(NlogN)了

T*u2017-01-19 08:01

10 楼

dp?

m*62017-01-19 08:01

11 楼

Input: Record[] records:
Function:
// sort records base on ending time from smallest to largest
sort (records);
int[] endings = new int[records.length];
int[] weights = new int[records.length];
endings[0] = records[0].ending;
weights[0] = records[0].weight;
for (int i = 1; i < records.length; i++)
{
// binary search array endings up to index i for j where j is the largest
value where endings[j] < records[i].starting O(logN)
// this search returns -1 if records[i].starting is smaller than all
values in endings
int j = getLargestIndex(endings, i, records[i].starting);
int startingWeight = j == -1 ? 0 : weights[j];
endings[i] = records[i].ending;
weights[i] = MAX(weights[i-1], records[i].weight + startingWeight);
}
return weights[records.length-1];

Runtime is O(NLogN) for both sorting and the loop

有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一个
set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。给个思....
....

【在 y***n 的大作中提到】

: 有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一个
: set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。
: 给个思路就行了。。

j*32017-01-19 08:01

12 楼

挖，你好牛阿，什么是lis？

index

【在 r*******k 的大作中提到】

: 好像可以进一步优化，类似LIS优化成O(NlgN)
: 之前的所有record的upper bound是排序了的。
: 用i+1个record的lower bound去upper bound里二分查找，可以找到不想交的最大index
: ，然后低于这个index的就不用比了。高于这个index的，由于相交了，也不用比了。
: 这需要另外一个数组X记录低于i的最大值。因为M[i]是以i结尾的最大值，并不是小于
: 等于i的最大值。
: 不过这么看，M都没有记录的必要了。。。
: 因为高于i的那些record，也就是和i+1有交集的，也有可能是最大值。
: 所以M[i+1]可以通过二分查找迅速算出，但X[i+1]必须用M[i+1]和X[i]比较之后算出

g*g2017-01-19 08:01

13 楼

看看我的解法。
// suppose all the beginning of all the records are in the increasing order
struct record
{
double begin;
double end;
double weight;
};
double getMaxWeight(double begin, double end, record* a, int number)
{
if (number == 1)
return (a[0].begin >= begin && a[0].end <= end)?a[0].weight:0;
else if (a[1].begin >= a[0].end)
return a[0].weight+getMaxWeight(a[1].begin, end, a+1, number-1);
else
return max(a[0].weight+getMaxWeight(a[0].end, end, a+2, number-2),
getMaxWeight(a[1].begin, end, a+1, number-1));
}