FB上amazon 25 off 75的没了 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Money - 海外理财

FB上amazon 25 off 75的没了

FB上amazon 25 off 75的没了# Money - 海外理财

i*72013-12-03 08:12

1 楼

You are given N ranges of date offsets when N employees are present in an
organization. Something like
1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day )
2-6
8-9
..
1-14
You have to organize an event on minimum number of days such that each
employee can attend the event at least twice. Write an algorithm (there is
apparently an O(n) algorithm for this).

H*72013-12-03 08:12

2 楼

唉呀

H*r2013-12-03 08:12

3 楼

"there is apparently an O(n) algorithm for this"
这个结论哪里来的？

【在 i*********7 的大作中提到】

: You are given N ranges of date offsets when N employees are present in an
: organization. Something like
: 1-4 (i.e. employee will come on 1st, 2nd, 3rd and 4th day )
: 2-6
: 8-9
: ..
: 1-14
: You have to organize an event on minimum number of days such that each
: employee can attend the event at least twice. Write an algorithm (there is
: apparently an O(n) algorithm for this).

i*72013-12-03 08:12

4 楼

我也不知道。。。careercup上面就这么写的。
我怎么有印象其实这应该是一道np问题？

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

: "there is apparently an O(n) algorithm for this"
: 这个结论哪里来的？

p*s2013-12-03 08:12

5 楼

收回前言，大牛们帮忙看看下面这个思路中不中，没证明：
首先显然有性质1：
对于两个employee ij有区间[ai,bi][aj,bj]满足ai<=aj<=bj<=bi，则可以不去考虑员
工i，满足j即可满足i。
因此如果对所有需要考虑的区间进行排序后，对于i和i+1有性质2：
要么ai<=aj<=bi<=bj（相交而不包含）
要么ai<=bi<=aj<=bj(不相交）
这里根据题目情景考虑，总日期数不会太多，而员工数可能很多，因此可以O(n)时间对
所有区间的ai进行排序，然后O(n)时间消除所有性质1中的包含情况，然后：
如果每个员工只出席一次的话，那其实只要贪心就好。即对当前员工i，让其在bi（最
后一天）开会，然后顺序的让与[ai,bi]相交的i+1,i+2..都在同一天开会，直到无法满
足时，再重复此步骤。这个也是o(n)
而出席2次的情况似乎可以推广得到，多记个数就行。

C*U2013-12-03 08:12

6 楼

sorting + greedy就可以做了
先把所有人根据末尾的时间排序用O(nlogn)时间
然后从头开始为每个人选取最晚的时间
比如第一个人是1-4，那么选取3-4两天办会议
如果有别的人和这两天重合，那么就可以把这个去掉了
否则为这个人选取最晚的可能的时间

【在 i*********7 的大作中提到】

s*a2013-12-03 08:12

7 楼

找出所有人最晚的到达时间T1，最早的离开时间T2一O(N)，然后选[T2-1, T1+1]为开会
时间如果T1>=T2-1，否则选[T1, T1+1]为开会时间。

【在 C***U 的大作中提到】

: sorting + greedy就可以做了
: 先把所有人根据末尾的时间排序用O(nlogn)时间
: 然后从头开始为每个人选取最晚的时间
: 比如第一个人是1-4，那么选取3-4两天办会议
: 如果有别的人和这两天重合，那么就可以把这个去掉了
: 否则为这个人选取最晚的可能的时间

w*x2013-12-03 08:12

8 楼

greedy啦, 就是最大event安排问题

f*22013-12-03 08:12

9 楼

I do not quite understand this problem.
For example,
1-4 (employee Ann comes on Day 1, 2, 3, 4)
2-6 (employee Bob comes on Day 2, 3, 4, 5, 6)
8-9 (employee Charles comes on Day 8, 9)
1-14 (employee David comes on 1, 2, ..., 14).
There is no way you can find a day when every employee agree on.

【在 i*********7 的大作中提到】

t*e2013-12-03 08:12

10 楼

In your example the answer is 3,4,5,6,7,8,9

【在 f*********2 的大作中提到】

: I do not quite understand this problem.
: For example,
: 1-4 (employee Ann comes on Day 1, 2, 3, 4)
: 2-6 (employee Bob comes on Day 2, 3, 4, 5, 6)
: 8-9 (employee Charles comes on Day 8, 9)
: 1-14 (employee David comes on 1, 2, ..., 14).
: There is no way you can find a day when every employee agree on.