r*******g
发帖数: 1335 | 1 https://www.glassdoor.com/Interview/Given-a-set-of-n-jobs-with-
end-time-cost-find-a-subset-so-that-no-2-jobs-overlap-and-the-cost-is-
maximum-QTN_440168.htm
Given a set of n jobs with [start time, end time, cost ] find a subset so
that no 2 jobs overlap and the cost is maximum ?
想了一下dp，但是状态转移不好写。
谢谢了。 |
r*******g
发帖数: 1335 | 2 似乎就是DP[i]表示到达时间i的时候能够得到的最大cost，先对interval 排序，然后
从小到大scan，每个新的interval I，可以更新DP[I.end]，这里需要注意的是DP[I.
end]更新后可能影响后面的若干个DP。
DP[i] = sum of cost of all intervals whose end time is smaller than i, and
have no overlap.
int currentGlobalEnd=0;
For each interval I:
DP[I.end] = max(DP[I.end], DP[I.begin]+cost_I);
for I.end to currentGlobalEnd: update their DP.
update currentGlobalEnd. |
m******0
发帖数: 222 | 3 1. sort the jobs by theirs start-times to non-descending order, resulted in
jobs[] (size=n)
2. define dp[i]: max cost of non-overlapping jobs from jobs[i to n-1]
3. to get dp[i], consider two choices:
1) use jobs[i]: let jobs[j] be the first job whose start-time >= jobs[i].
end, then cost1 = (jobs[i].cost + dp[j])
2) not use jobs[i]: cost2 = dp[i+1]
dp[i] = max(cost1, cost2) |
g******d
发帖数: 152 | |
r*******g
发帖数: 1335 | 5
in
你这是不是写错了，应该是jobs[j] end time <= jobs[i]吧。而且即使这样，search
开销是不是n?最后开销是n^2?
【在 m******0 的大作中提到】
: 1. sort the jobs by theirs start-times to non-descending order, resulted in
: jobs[] (size=n)
: 2. define dp[i]: max cost of non-overlapping jobs from jobs[i to n-1]
: 3. to get dp[i], consider two choices:
: 1) use jobs[i]: let jobs[j] be the first job whose start-time >= jobs[i].
: end, then cost1 = (jobs[i].cost + dp[j])
: 2) not use jobs[i]: cost2 = dp[i+1]
: dp[i] = max(cost1, cost2)
|
b********6
发帖数: 35437 | 6 先排序再binary search，结果应该是n log n
search
【在 r*******g 的大作中提到】
:
: in
: 你这是不是写错了，应该是jobs[j] end time <= jobs[i]吧。而且即使这样，search
: 开销是不是n?最后开销是n^2?
|
r*******g
发帖数: 1335 | 7 排序是对starttime排序，现在是要找endtime小于当前starttime的，对吧？
这题肯定可以做，就是怎么写比较简洁。
【在 b********6 的大作中提到】
: 先排序再binary search，结果应该是n log n
:
: search
|
b********6
发帖数: 35437 | 8 对end time排序，遍历所有event就可以得出结果
dynamical programing弄一个有n个元素的数组result[n]，n是job的数目，里面存
maximum total cost
对于第i个job，把start time记作ts，取不取这个job决定于result[i-1]和cost_i +
result[j]的大小，j是ts之前end time最接近ts的job的index, 如果前者大，则不取这
个job，如果后者大，则取这个job并调整subset里的元素
时间复杂度就是一开始的排序，和后来binary search j，都是n log n，如果使用遍历
查找，就是n^2。其他操作全部是O(1)
【在 r*******g 的大作中提到】
: 排序是对starttime排序，现在是要找endtime小于当前starttime的，对吧？
: 这题肯定可以做，就是怎么写比较简洁。
|
r*******g
发帖数: 1335 | 9 按照endtime排序好，受教了。
thanks
【在 b********6 的大作中提到】
: 对end time排序，遍历所有event就可以得出结果
: dynamical programing弄一个有n个元素的数组result[n]，n是job的数目，里面存
: maximum total cost
: 对于第i个job，把start time记作ts，取不取这个job决定于result[i-1]和cost_i +
: result[j]的大小，j是ts之前end time最接近ts的job的index, 如果前者大，则不取这
: 个job，如果后者大，则取这个job并调整subset里的元素
: 时间复杂度就是一开始的排序，和后来binary search j，都是n log n，如果使用遍历
: 查找，就是n^2。其他操作全部是O(1)
|
k***g
发帖数: 166 | 10 大家说的都是求maximum cost，但题目说的是find a subset that..
如果是要取这个subset应该怎么做呢？ |
b********6
发帖数: 35437 | 11 弄两个数组，A[n], B[n] where n is the number of jobs，然后再用一个变量来存总
cost，如果想把每一步的总cost和每一步的subset size存起来的话，也可以多弄几个
数组。
A[i] 存从0 - i个job的最优解subset的最后一个job的index
B[i] 存A[i]对应的最优解subset的倒数第二个job的index
比如对于一个5个job的输入数组，A[4]=3，表示这5个输入的最优解subset的最后一个
job的index为3, 然后B[4]=2，表示取完3之后要去取2，然后找A[2]=1，然后找B[2]，
一路找一下去，时间复杂度是O(k)，k是subset的size
【在 k***g 的大作中提到】
: 大家说的都是求maximum cost，但题目说的是find a subset that..
: 如果是要取这个subset应该怎么做呢？
|
