y***n
发帖数: 1594 | 1 有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一个
set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。
给个思路就行了。。 |
s*********s
发帖数: 5 | 2 先排序
在排序后的数组里定义m[i]表示以i结尾的最大权重
m[i] = max(m[k] + weight[k]) 其中k的结束时间小于i的开始时间
时间复杂度O(N^2) |
y***n
发帖数: 1594 | 3 DP ?
【在 s*********s 的大作中提到】
: 先排序
: 在排序后的数组里定义m[i]表示以i结尾的最大权重
: m[i] = max(m[k] + weight[k]) 其中k的结束时间小于i的开始时间
: 时间复杂度O(N^2)
|
r*******k
发帖数: 1423 | 4 怎么看着那么像LIS问题
不过好像没办法向LIS那样继续优化到 O(NlogN)了
【在 s*********s 的大作中提到】
: 先排序
: 在排序后的数组里定义m[i]表示以i结尾的最大权重
: m[i] = max(m[k] + weight[k]) 其中k的结束时间小于i的开始时间
: 时间复杂度O(N^2)
|
r*******k
发帖数: 1423 | 5 好像可以进一步优化，类似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*****u
发帖数: 7103 | |
m********6
发帖数: 58 | 7 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**********3
发帖数: 3211 | 8 挖，你好牛阿，什么是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******g
发帖数: 289 | 9 看看我的解法。
// 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));
} |
b********r
发帖数: 620 | 10 what if the last record weigh most? how your formula accounts for that case?
【在 s*********s 的大作中提到】
: 先排序
: 在排序后的数组里定义m[i]表示以i结尾的最大权重
: m[i] = max(m[k] + weight[k]) 其中k的结束时间小于i的开始时间
: 时间复杂度O(N^2)
|
|
|
w**t
发帖数: 893 | 11 排序，dp binary search, o(nlogN)
【在 y***n 的大作中提到】
: 有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一个
: set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。
: 给个思路就行了。。
|
w**t
发帖数: 893 | 12 btw, space o(N)
【在 w**t 的大作中提到】
: 排序，dp binary search, o(nlogN)
|
r****7
发帖数: 2282 | 13 看样子没法greedy，按结束时间排序然后DP得了
【在 y***n 的大作中提到】
: 有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一个
: set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。
: 给个思路就行了。。
|
h****g
发帖数: 105 | 14 有一个思路是用directed acyclic graph. 定义节点是interval，两个intervel如果没
有重叠，那么他们之间有一个edge，从小intervel 指向大intervel 这样问题就转化成
了求带权重的最大路径 |
b******g
发帖数: 3616 | 15 这个思路好！很形象！不过建图本身可能就要o(n^2)了吧？
【在 h****g 的大作中提到】
: 有一个思路是用directed acyclic graph. 定义节点是interval，两个intervel如果没
: 有重叠，那么他们之间有一个edge，从小intervel 指向大intervel 这样问题就转化成
: 了求带权重的最大路径
|
b********r
发帖数: 620 | 16 好像不简单，是要你写程序实现，还是只是说说想法。
【在 y***n 的大作中提到】
: 有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一个
: set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。
: 给个思路就行了。。
|
j*d
发帖数: 96 | 17
你quote里面写着的
【在 y***n 的大作中提到】
: 有一组records，每个record由三个参数组成，开始时间，结束时间，权重。找到一个
: set，这个set包含的records在时间上没有重叠，并且set的权重之和最大。
: 给个思路就行了。。
|
s**********k
发帖数: 88 | 18 我觉得应该是
m[i]=Max(m[k]+weight[i], m[k+1], ...,m[i-1)
其中k的结束时间小于但最接近i的开始时间.时间复杂度应该是n的平方
【在 s*********s 的大作中提到】
: 先排序
: 在排序后的数组里定义m[i]表示以i结尾的最大权重
: m[i] = max(m[k] + weight[k]) 其中k的结束时间小于i的开始时间
: 时间复杂度O(N^2)
|
