大家怀孕后又没有控制不住尿的时候？ - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>NextGeneration - 我爱宝宝

大家怀孕后又没有控制不住尿的时候？

大家怀孕后又没有控制不住尿的时候？# NextGeneration - 我爱宝宝

r*g2010-05-18 07:05

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，但是状态转移不好写。
谢谢了。

x*62010-05-18 07:05

2 楼

我打喷嚏的时候总是会尿出来一点，郁闷死了。

r*g2010-05-18 07:05

3 楼

似乎就是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.

s*n2010-05-18 07:05

4 楼

我吐得很厉害的时候会有漏尿，极度郁闷

【在 x********6 的大作中提到】

: 我打喷嚏的时候总是会尿出来一点，郁闷死了。

m*02010-05-18 07:05

5 楼

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)

c*u2010-05-18 07:05

6 楼

生完就好了。

【在 x********6 的大作中提到】

: 我打喷嚏的时候总是会尿出来一点，郁闷死了。

g*d2010-05-18 07:05

7 楼

https://www.youtube.com/watch?v=cr6Ip0J9izc

G*02010-05-18 07:05

8 楼

我也是，每次喷嚏了都这样。

r*g2010-05-18 07:05

9 楼

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)

o*t2010-05-18 07:05

10 楼

正常

b*62010-05-18 07:05

11 楼

先排序再binary search，结果应该是n log n

search

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

:
: in
: 你这是不是写错了，应该是jobs[j] end time <= jobs[i]吧。而且即使这样，search
: 开销是不是n?最后开销是n^2?

q*22010-05-18 07:05

12 楼

我也是,32周开始.尿不能憋一秒钟,偶而也漏尿.并且宝宝一动就老是想尿尿,下腹有时
还不太舒服,这正常啊?

r*g2010-05-18 07:05

13 楼

排序是对starttime排序，现在是要找endtime小于当前starttime的，对吧？
这题肯定可以做，就是怎么写比较简洁。

【在 b********6 的大作中提到】

: 先排序再binary search，结果应该是n log n
:
: search

b*s2010-05-18 07:05

14 楼

因为孕期体内释放relaxin，把肌肉和关节都给松弛了
对策就是Kegel锻炼pelvic floor

【在 x********6 的大作中提到】

: 我打喷嚏的时候总是会尿出来一点，郁闷死了。

b*62010-05-18 07:05

15 楼

对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的，对吧？
: 这题肯定可以做，就是怎么写比较简洁。

j*d2010-05-18 07:05

16 楼

这个越到生前越是如此，很正常。

【在 x********6 的大作中提到】

: 我打喷嚏的时候总是会尿出来一点，郁闷死了。

r*g2010-05-18 07:05

17 楼

按照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)

h*r2010-05-18 07:05

18 楼

我刚怀孕就开始漏尿了，所以打喷嚏的时候必须夹紧腿。

k*g2010-05-18 07:05

19 楼

大家说的都是求maximum cost，但题目说的是find a subset that..
如果是要取这个subset应该怎么做呢？

l*22010-05-18 07:05

20 楼

我生后8个月了，有时还这样。郁闷啊！

b*62010-05-18 07:05

21 楼

弄两个数组，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应该怎么做呢？