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应该怎么做呢?
|