logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
A facebook interview question
avatar
A facebook interview question# JobHunting - 待字闺中
b*7
1 楼
ou 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).
How to solve this? I am not sure if greedy algorithm works. Please advise,
thanks!
avatar
z*w
2 楼
what do you mean by "attend the event at least twice"?
avatar
c*g
3 楼
怎么没有人讨论这题？

【在 b******7 的大作中提到】
: ou 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).
avatar
c*g
4 楼
怎么没有人讨论这题？

【在 b******7 的大作中提到】
: ou 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).
avatar
m*a
5 楼
扫描一遍找到所有人中最晚的开始时间t1和最早的结束时间t2.
如果t1 >= t2-1, event 就t2-1 开始， t1+1 结束，最小天数t1-t2 +2
如果t1 < t2-1, 最小天数就是2天。
avatar
m*a
6 楼
can attend 就是说这个时间段内每个人有2天吧。
加一个条件，如果扫描的时候任何一个人只有一天来的话 ， 直接报错。
avatar
c*g
7 楼
显然不对啊
假设时间段是 1-3， 4-6， 7-9
按照你的，最大的时间是9（t2）， 最小的时间是1(t1)
但是，这个给定的时间段，显然返回的无解。

【在 m**a 的大作中提到】
: 扫描一遍找到所有人中最晚的开始时间t1和最早的结束时间t2.
: 如果t1 >= t2-1, event 就t2-1 开始， t1+1 结束，最小天数t1-t2 +2
: 如果t1 < t2-1, 最小天数就是2天。
avatar
m*a
8 楼
看清楚定义： 最“早”的结束时间 t2 是3， 最“晚”的开始时间t1是7
所以是2~8， 共7天。

【在 c***g 的大作中提到】
: 显然不对啊
: 假设时间段是 1-3， 4-6， 7-9
: 按照你的，最大的时间是9（t2）， 最小的时间是1(t1)
: 但是，这个给定的时间段，显然返回的无解。
avatar
e*l
9 楼
为什么结果不是一系列离散的日期呢
avatar
m*a
10 楼
有道理 我可能理解错了 想的简单了

【在 e***l 的大作中提到】
: 为什么结果不是一系列离散的日期呢
avatar
e*l
11 楼
我有个思路。
假定N个区间都是以结束日期的早晚排序，记为a1,a2,...an. 第一个人结束的最早。
首先选中第一个人的最后两天，a1-1和a1。给和这两天有重叠的人上标记，1个或2个。
继续选中下一个a2，如果此人没有标记，还是选最后两天a2-1和a2。如果有1个标记，
只选中最后一天。如果有2个标记，直接pass。再继续上标记。
继续直到an。
如果这些日期的最大值是m的话，可以做到O(mn)。
avatar
e*l
12 楼
主要原理是尽量往后安排，只要没有人因此而错过。初步觉得是最优的。有没有人给个
反例？
avatar
p*2
13 楼
这题O(n)好像不容易呀。
avatar
p*2
14 楼

我也是这个思路，先排序，然后挨个查找，这样就是O(nlogn)复杂度。想不到O(n)的解
法。

【在 e***l 的大作中提到】
: 我有个思路。
: 假定N个区间都是以结束日期的早晚排序，记为a1,a2,...an. 第一个人结束的最早。
: 首先选中第一个人的最后两天，a1-1和a1。给和这两天有重叠的人上标记，1个或2个。
: 继续选中下一个a2，如果此人没有标记，还是选最后两天a2-1和a2。如果有1个标记，
: 只选中最后一天。如果有2个标记，直接pass。再继续上标记。
: 继续直到an。
: 如果这些日期的最大值是m的话，可以做到O(mn)。
avatar
e*l
15 楼
如果这些日期的最大值是O(1)的话，可以做到O(n)。不必前先排序。
avatar
p*2
16 楼

怎么搞？

【在 e***l 的大作中提到】
: 如果这些日期的最大值是O(1)的话，可以做到O(n)。不必前先排序。
avatar
e*l
17 楼
想象一下counting sort。直接从day1开始，每次花O(N)查找有没有要结束的区间。
avatar
p*2
18 楼

我觉得天数会大于n， 所以这样还不如nlogn呢。

【在 e***l 的大作中提到】
: 想象一下counting sort。直接从day1开始，每次花O(N)查找有没有要结束的区间。
avatar
p*u
19 楼
1, get the ending days of N ranges, then sort increase and unique
2, enumerate the sorted days, from lower to higher:
on this day, find out the employees whose ending day is this day: then
according to the events they have attended, decide you should schedule 0, 1
or 2 events on this day; and update the events other employees have attended.
3, get the final number of days to schedule events
but the algorithm complexity is O(NlogN)

【在 b******7 的大作中提到】
: ou 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).
avatar
r*n
20 楼
sort is nlogn

1
attended.

【在 p*u 的大作中提到】
: 1, get the ending days of N ranges, then sort increase and unique
: 2, enumerate the sorted days, from lower to higher:
: on this day, find out the employees whose ending day is this day: then
: according to the events they have attended, decide you should schedule 0, 1
: or 2 events on this day; and update the events other employees have attended.
: 3, get the final number of days to schedule events
: but the algorithm complexity is O(NlogN)
avatar
h*e
21 楼
well.. we have to assume we can use O(n) bucket sort.. since date is of
fixed range.. sort of. Then, we just need to keep an eye on the last three
events when an employee comes or leaves.. the last one is pending to be
scheduled. Whether it can be delayed or not depends on the first two.. One
sweep over the sorted come and leave dates will solve the problem..
avatar
i*h
22 楼
如果用bucket的话,
最后的sweep是否是 O(k), k是bucket的数目, k>=n ?

three

【在 h********e 的大作中提到】
: well.. we have to assume we can use O(n) bucket sort.. since date is of
: fixed range.. sort of. Then, we just need to keep an eye on the last three
: events when an employee comes or leaves.. the last one is pending to be
: scheduled. Whether it can be delayed or not depends on the first two.. One
: sweep over the sorted come and leave dates will solve the problem..
avatar
h*e
23 楼
non empty bucket is at most 2n.. so that is fine. The point is once it is
sorted, everything is simple. Just use a greedy strategy: schedule a meeting
on the last possible date.

【在 i***h 的大作中提到】
: 如果用bucket的话,
: 最后的sweep是否是 O(k), k是bucket的数目, k>=n ?
:
: three
avatar
b*u
24 楼
我觉得是sort by end time，每次选最小end date和end date-1，然后除掉有两个date
的人。如果有人start on this end date，记录他已经有一天了。反复找剩下人中最早
end的。
说的不太清楚，但face to face能讲明白这是对的应该。

【在 b******7 的大作中提到】
: ou 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).
avatar
s*r
25 楼
我怎么觉得这个事NP complete的， 可以转成set cover 问题。
把所有的人看成universal set，每一天都对应一个subset，对应这一天哪些人有空，
题目就是变成找最小的set cover问题。这个看起来是NP C问题。只能用approximation
algorithm
avatar
h*e
26 楼
man.. this is a very easy problem...
avatar
i*h
27 楼
前面都已经给出贪婪酸法了...
唯一问题就是这个O(N)

approximation

【在 s********r 的大作中提到】
: 我怎么觉得这个事NP complete的， 可以转成set cover 问题。
: 把所有的人看成universal set，每一天都对应一个subset，对应这一天哪些人有空，
: 题目就是变成找最小的set cover问题。这个看起来是NP C问题。只能用approximation
: algorithm
avatar
H*1
28 楼
i=1:N
if(t1[i] >= t2[i])
fail();
maxeventstart = min(t2)-1;
mineventend = max(t1) + 1;
if(maxeventstart >= mineventend)
organizeEvent(maxeventstart, maxeventstart +1 );
else
organizeEvent(maxeventStart, mineventend);

【在 b******7 的大作中提到】
: ou 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).
avatar
i*h
29 楼
你扫描bucket的时候, 每个空的桶也要查是不是为空, 是O(1), 不是免费的

【在 h********e 的大作中提到】
: man.. this is a very easy problem...
avatar
s*r
30 楼
前面的greedy algorithm都没讲这个思想，还有我不懂搞bucket sort对解决问题有啥
帮助

【在 i***h 的大作中提到】
: 前面都已经给出贪婪酸法了...
: 唯一问题就是这个O(N)
:
: approximation
avatar
i*h
31 楼
有最多 NlgN 的算法怎么还会是 NP complete

【在 s********r 的大作中提到】
: 前面的greedy algorithm都没讲这个思想，还有我不懂搞bucket sort对解决问题有啥
: 帮助
avatar
s*r
32 楼
上面提到的NlgN的算法都没有办法证明其正确性。
难道是我对题目理解有误？

【在 i***h 的大作中提到】
: 有最多 NlgN 的算法怎么还会是 NP complete
avatar
h*e
33 楼
anyway.. for sorting number in FIXED range, the sorting time is O(n). I
shouldn't say using bucket sort. It is actually Radix sort. It is like
cheating, but facebook likes such kind of cheating. They allow you to use
fixed hash function to solve algorithmic problems, which is not always good
if you consider the worst case analysis.
avatar
i*h
34 楼
应该是你理解错了

【在 s********r 的大作中提到】
: 上面提到的NlgN的算法都没有办法证明其正确性。
: 难道是我对题目理解有误？
avatar
e*l
35 楼

approximation
假设每个人的日期可以是不连续的，可以转换成set cover。
但是这里每个人是连续的区间，简化了这个问题。

【在 s********r 的大作中提到】
: 我怎么觉得这个事NP complete的， 可以转成set cover 问题。
: 把所有的人看成universal set，每一天都对应一个subset，对应这一天哪些人有空，
: 题目就是变成找最小的set cover问题。这个看起来是NP C问题。只能用approximation
: algorithm
avatar
e*l
36 楼

good
it's counting sort.

【在 h********e 的大作中提到】
: anyway.. for sorting number in FIXED range, the sorting time is O(n). I
: shouldn't say using bucket sort. It is actually Radix sort. It is like
: cheating, but facebook likes such kind of cheating. They allow you to use
: fixed hash function to solve algorithmic problems, which is not always good
: if you consider the worst case analysis.
avatar
s*r
37 楼
题目里面没有要求说每个人参加event的date必须是连续的

【在 e***l 的大作中提到】
:
: good
: it's counting sort.
avatar
H*1
38 楼
min(t2)-1 一直到 max(t1) + 1
是2 - 8啊
你怎么说人家返回无解呢

【在 c***g 的大作中提到】
: 显然不对啊
: 假设时间段是 1-3， 4-6， 7-9
: 按照你的，最大的时间是9（t2）， 最小的时间是1(t1)
: 但是，这个给定的时间段，显然返回的无解。
avatar
i*h
39 楼
你非要用集合论接当然可以
但是这个问题被证明排序以后有最优解

【在 s********r 的大作中提到】
: 题目里面没有要求说每个人参加event的date必须是连续的
avatar
i*h
40 楼
bucket sort average is O(n + k) if you need to sweep final sorted sequence.

good

【在 h********e 的大作中提到】
: anyway.. for sorting number in FIXED range, the sorting time is O(n). I
: shouldn't say using bucket sort. It is actually Radix sort. It is like
: cheating, but facebook likes such kind of cheating. They allow you to use
: fixed hash function to solve algorithmic problems, which is not always good
: if you consider the worst case analysis.
avatar
e*l
41 楼

每个人的available dates是连续的

【在 s********r 的大作中提到】
: 题目里面没有要求说每个人参加event的date必须是连续的
avatar
b*u
42 楼
谁解释下buck sort怎么解这个？
avatar
y*z
43 楼
我用了 基序排序， 这样能达到线性时间。
复杂度是 max(O(M)，O(N))
M是date的最大的数
N是数组的长度
code wins arguments.
欢迎拍砖
#define GREEDY_EVENT
#ifdef GREEDY_EVENT
#include
#include
#include
using namespace std;
int main(){
const int n = 5;
int sstart[n] = {1,8,2,11,15};
int eend[n] = {4,9,6,14,18};
for(int i=0;icout<}
cout<const int MAXDATE = 100;
int radix[MAXDATE]={0};
int final[n];
for(int i=0;ifor(int i=1;ifor(int i=n-1;i>=0;i--) final[--radix[eend[i]]] = i;
//after sort
for(int i=0;icout<}
//greedy algorithm
int e1 = eend[final[0]];//last two days
int e2 = e1-1;//last two days
vector schedule;
for(int i=1;iif(sstart[final[i]]>e1){
schedule.push_back(e2);
schedule.push_back(e1);
e1 = eend[final[i]];
e2 = e1-1;
}
}
if(schedule[schedule.size()-1] < e2){
schedule.push_back(e2);
schedule.push_back(e1);
}
for(int i=0;icout<}
cout<return 0;
}
#endif
avatar
h*w
44 楼
我就靠了，
各位亲们你们怎么能用sort解决！！！？？？
我给个解法吧， time complex is O(n)
建立N*31矩阵
each row element marks 1 if people available that day
EXP,
1~17 is a duration, then a[0,1] to a[0, 17] is all 1.

Of course the build time is not counted as the decision made time,
So sum every col, you got the max value (time cost O(31n)), mark
corresponding row flag value 1, till you reach a row with flag value 2, fake
delete such row, till every row is fake deleted.
How many max value you computed before all rows are faked deleted,
you find the min days to arrange the conference.
Hahaha!
avatar
r*n
45 楼
哪说了一定是同一个月之内啊....

fake

【在 h********w 的大作中提到】
: 我就靠了，
: 各位亲们你们怎么能用sort解决！！！？？？
: 我给个解法吧， time complex is O(n)
: 建立N*31矩阵
: each row element marks 1 if people available that day
: EXP,
: 1~17 is a duration, then a[0,1] to a[0, 17] is all 1.
:
: Of course the build time is not counted as the decision made time,
: So sum every col, you got the max value (time cost O(31n)), mark
avatar
h*w
46 楼
那我问你，数据是1－17，又没说1/1 to 17/1。 我理解是一个月内有什么不对？

【在 r*******n 的大作中提到】
: 哪说了一定是同一个月之内啊....
:
: fake
avatar
r*n
47 楼
你理解半个月之内也可以...总之我没体会出来.....

【在 h********w 的大作中提到】
: 那我问你，数据是1－17，又没说1/1 to 17/1。 我理解是一个月内有什么不对？
avatar
e*l
48 楼
一年也就365天，十年才3650天，一辈子也活不到30000天。认为天数最大是O(1)也无不
妥，呵呵。人数可以有十万百万什么的，比如富士康。
avatar
b*7
49 楼
ou 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).
How to solve this? I am not sure if greedy algorithm works. Please advise,
thanks!
avatar
z*w
50 楼
what do you mean by "attend the event at least twice"?
avatar
c*g
51 楼
怎么没有人讨论这题？

【在 b******7 的大作中提到】
: ou 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).
avatar
c*g
52 楼
怎么没有人讨论这题？

【在 b******7 的大作中提到】
: ou 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).
avatar
m*a
53 楼
扫描一遍找到所有人中最晚的开始时间t1和最早的结束时间t2.
如果t1 >= t2-1, event 就t2-1 开始， t1+1 结束，最小天数t1-t2 +2
如果t1 < t2-1, 最小天数就是2天。
avatar
m*a
54 楼
can attend 就是说这个时间段内每个人有2天吧。
加一个条件，如果扫描的时候任何一个人只有一天来的话 ， 直接报错。
avatar
c*g
55 楼
显然不对啊
假设时间段是 1-3， 4-6， 7-9
按照你的，最大的时间是9（t2）， 最小的时间是1(t1)
但是，这个给定的时间段，显然返回的无解。

【在 m**a 的大作中提到】
: 扫描一遍找到所有人中最晚的开始时间t1和最早的结束时间t2.
: 如果t1 >= t2-1, event 就t2-1 开始， t1+1 结束，最小天数t1-t2 +2
: 如果t1 < t2-1, 最小天数就是2天。
avatar
m*a
56 楼
看清楚定义： 最“早”的结束时间 t2 是3， 最“晚”的开始时间t1是7
所以是2~8， 共7天。

【在 c***g 的大作中提到】
: 显然不对啊
: 假设时间段是 1-3， 4-6， 7-9
: 按照你的，最大的时间是9（t2）， 最小的时间是1(t1)
: 但是，这个给定的时间段，显然返回的无解。
avatar
e*l
57 楼
为什么结果不是一系列离散的日期呢
avatar
m*a
58 楼
有道理 我可能理解错了 想的简单了

【在 e***l 的大作中提到】
: 为什么结果不是一系列离散的日期呢
avatar
e*l
59 楼
我有个思路。
假定N个区间都是以结束日期的早晚排序，记为a1,a2,...an. 第一个人结束的最早。
首先选中第一个人的最后两天，a1-1和a1。给和这两天有重叠的人上标记，1个或2个。
继续选中下一个a2，如果此人没有标记，还是选最后两天a2-1和a2。如果有1个标记，
只选中最后一天。如果有2个标记，直接pass。再继续上标记。
继续直到an。
如果这些日期的最大值是m的话，可以做到O(mn)。
avatar
e*l
60 楼
主要原理是尽量往后安排，只要没有人因此而错过。初步觉得是最优的。有没有人给个
反例？
avatar
p*2
61 楼
这题O(n)好像不容易呀。
avatar
p*2
62 楼

我也是这个思路，先排序，然后挨个查找，这样就是O(nlogn)复杂度。想不到O(n)的解
法。

【在 e***l 的大作中提到】
: 我有个思路。
: 假定N个区间都是以结束日期的早晚排序，记为a1,a2,...an. 第一个人结束的最早。
: 首先选中第一个人的最后两天，a1-1和a1。给和这两天有重叠的人上标记，1个或2个。
: 继续选中下一个a2，如果此人没有标记，还是选最后两天a2-1和a2。如果有1个标记，
: 只选中最后一天。如果有2个标记，直接pass。再继续上标记。
: 继续直到an。
: 如果这些日期的最大值是m的话，可以做到O(mn)。
avatar
e*l
63 楼
如果这些日期的最大值是O(1)的话，可以做到O(n)。不必前先排序。
avatar
p*2
64 楼

怎么搞？

【在 e***l 的大作中提到】
: 如果这些日期的最大值是O(1)的话，可以做到O(n)。不必前先排序。
avatar
e*l
65 楼
想象一下counting sort。直接从day1开始，每次花O(N)查找有没有要结束的区间。
avatar
p*2
66 楼

我觉得天数会大于n， 所以这样还不如nlogn呢。

【在 e***l 的大作中提到】
: 想象一下counting sort。直接从day1开始，每次花O(N)查找有没有要结束的区间。
avatar
p*u
67 楼
1, get the ending days of N ranges, then sort increase and unique
2, enumerate the sorted days, from lower to higher:
on this day, find out the employees whose ending day is this day: then
according to the events they have attended, decide you should schedule 0, 1
or 2 events on this day; and update the events other employees have attended.
3, get the final number of days to schedule events
but the algorithm complexity is O(NlogN)

【在 b******7 的大作中提到】
: ou 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).
avatar
r*n
68 楼
sort is nlogn

1
attended.

【在 p*u 的大作中提到】
: 1, get the ending days of N ranges, then sort increase and unique
: 2, enumerate the sorted days, from lower to higher:
: on this day, find out the employees whose ending day is this day: then
: according to the events they have attended, decide you should schedule 0, 1
: or 2 events on this day; and update the events other employees have attended.
: 3, get the final number of days to schedule events
: but the algorithm complexity is O(NlogN)
avatar
h*e
69 楼
well.. we have to assume we can use O(n) bucket sort.. since date is of
fixed range.. sort of. Then, we just need to keep an eye on the last three
events when an employee comes or leaves.. the last one is pending to be
scheduled. Whether it can be delayed or not depends on the first two.. One
sweep over the sorted come and leave dates will solve the problem..
avatar
i*h
70 楼
如果用bucket的话,
最后的sweep是否是 O(k), k是bucket的数目, k>=n ?

three

【在 h********e 的大作中提到】
: well.. we have to assume we can use O(n) bucket sort.. since date is of
: fixed range.. sort of. Then, we just need to keep an eye on the last three
: events when an employee comes or leaves.. the last one is pending to be
: scheduled. Whether it can be delayed or not depends on the first two.. One
: sweep over the sorted come and leave dates will solve the problem..
avatar
h*e
71 楼
non empty bucket is at most 2n.. so that is fine. The point is once it is
sorted, everything is simple. Just use a greedy strategy: schedule a meeting
on the last possible date.

【在 i***h 的大作中提到】
: 如果用bucket的话,
: 最后的sweep是否是 O(k), k是bucket的数目, k>=n ?
:
: three
avatar
b*u
72 楼
我觉得是sort by end time，每次选最小end date和end date-1，然后除掉有两个date
的人。如果有人start on this end date，记录他已经有一天了。反复找剩下人中最早
end的。
说的不太清楚，但face to face能讲明白这是对的应该。

【在 b******7 的大作中提到】
: ou 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).
avatar
s*r
73 楼
我怎么觉得这个事NP complete的， 可以转成set cover 问题。
把所有的人看成universal set，每一天都对应一个subset，对应这一天哪些人有空，
题目就是变成找最小的set cover问题。这个看起来是NP C问题。只能用approximation
algorithm
avatar
h*e
74 楼
man.. this is a very easy problem...
avatar
i*h
75 楼
前面都已经给出贪婪酸法了...
唯一问题就是这个O(N)

approximation

【在 s********r 的大作中提到】
: 我怎么觉得这个事NP complete的， 可以转成set cover 问题。
: 把所有的人看成universal set，每一天都对应一个subset，对应这一天哪些人有空，
: 题目就是变成找最小的set cover问题。这个看起来是NP C问题。只能用approximation
: algorithm
avatar
H*1
76 楼
i=1:N
if(t1[i] >= t2[i])
fail();
maxeventstart = min(t2)-1;
mineventend = max(t1) + 1;
if(maxeventstart >= mineventend)
organizeEvent(maxeventstart, maxeventstart +1 );
else
organizeEvent(maxeventStart, mineventend);

【在 b******7 的大作中提到】
: ou 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).
avatar
i*h
77 楼
你扫描bucket的时候, 每个空的桶也要查是不是为空, 是O(1), 不是免费的

【在 h********e 的大作中提到】
: man.. this is a very easy problem...
avatar
s*r
78 楼
前面的greedy algorithm都没讲这个思想，还有我不懂搞bucket sort对解决问题有啥
帮助

【在 i***h 的大作中提到】
: 前面都已经给出贪婪酸法了...
: 唯一问题就是这个O(N)
:
: approximation
avatar
i*h
79 楼
有最多 NlgN 的算法怎么还会是 NP complete

【在 s********r 的大作中提到】
: 前面的greedy algorithm都没讲这个思想，还有我不懂搞bucket sort对解决问题有啥
: 帮助
avatar
s*r
80 楼
上面提到的NlgN的算法都没有办法证明其正确性。
难道是我对题目理解有误？

【在 i***h 的大作中提到】
: 有最多 NlgN 的算法怎么还会是 NP complete
avatar
h*e
81 楼
anyway.. for sorting number in FIXED range, the sorting time is O(n). I
shouldn't say using bucket sort. It is actually Radix sort. It is like
cheating, but facebook likes such kind of cheating. They allow you to use
fixed hash function to solve algorithmic problems, which is not always good
if you consider the worst case analysis.
avatar
i*h
82 楼
应该是你理解错了

【在 s********r 的大作中提到】
: 上面提到的NlgN的算法都没有办法证明其正确性。
: 难道是我对题目理解有误？
avatar
e*l
83 楼

approximation
假设每个人的日期可以是不连续的，可以转换成set cover。
但是这里每个人是连续的区间，简化了这个问题。

【在 s********r 的大作中提到】
: 我怎么觉得这个事NP complete的， 可以转成set cover 问题。
: 把所有的人看成universal set，每一天都对应一个subset，对应这一天哪些人有空，
: 题目就是变成找最小的set cover问题。这个看起来是NP C问题。只能用approximation
: algorithm
avatar
e*l
84 楼

good
it's counting sort.

【在 h********e 的大作中提到】
: anyway.. for sorting number in FIXED range, the sorting time is O(n). I
: shouldn't say using bucket sort. It is actually Radix sort. It is like
: cheating, but facebook likes such kind of cheating. They allow you to use
: fixed hash function to solve algorithmic problems, which is not always good
: if you consider the worst case analysis.
avatar
s*r
85 楼
题目里面没有要求说每个人参加event的date必须是连续的

【在 e***l 的大作中提到】
:
: good
: it's counting sort.
avatar
H*1
86 楼
min(t2)-1 一直到 max(t1) + 1
是2 - 8啊
你怎么说人家返回无解呢

【在 c***g 的大作中提到】
: 显然不对啊
: 假设时间段是 1-3， 4-6， 7-9
: 按照你的，最大的时间是9（t2）， 最小的时间是1(t1)
: 但是，这个给定的时间段，显然返回的无解。
avatar
i*h
87 楼
你非要用集合论接当然可以
但是这个问题被证明排序以后有最优解

【在 s********r 的大作中提到】
: 题目里面没有要求说每个人参加event的date必须是连续的
avatar
i*h
88 楼
bucket sort average is O(n + k) if you need to sweep final sorted sequence.

good

【在 h********e 的大作中提到】
: anyway.. for sorting number in FIXED range, the sorting time is O(n). I
: shouldn't say using bucket sort. It is actually Radix sort. It is like
: cheating, but facebook likes such kind of cheating. They allow you to use
: fixed hash function to solve algorithmic problems, which is not always good
: if you consider the worst case analysis.
avatar
e*l
89 楼

每个人的available dates是连续的

【在 s********r 的大作中提到】
: 题目里面没有要求说每个人参加event的date必须是连续的
avatar
b*u
90 楼
谁解释下buck sort怎么解这个？
avatar
y*z
91 楼
我用了 基序排序， 这样能达到线性时间。
复杂度是 max(O(M)，O(N))
M是date的最大的数
N是数组的长度
code wins arguments.
欢迎拍砖
#define GREEDY_EVENT
#ifdef GREEDY_EVENT
#include
#include
#include
#include
using namespace std;
int main(){
srand(size_t(time(0)));
const int n = 5;
int sstart[n] = {1,8,2,11,15};
int eend[n] = {4,9,6,14,18};
for(int i=0;ifor(int i=0;ifor(int i=0;icout<}
cout<const int MAXDATE = 100;
int radix[MAXDATE]={0};
int final[n];
for(int i=0;ifor(int i=1;ifor(int i=n-1;i>=0;i--) final[--radix[eend[i]]] = i;
//after sort
for(int i=0;icout<<}
//greedy algorithm
int e1 = eend[final[0]];//last two days
int e2 = e1-1;//last two days
vector schedule;
for(int i=1;iif(sstart[final[i]]>e1){
schedule.push_back(e2);
schedule.push_back(e1);
e1 = eend[final[i]];
e2 = e1-1;
}else if(schedule.size()>0){
int last = schedule[schedule.size()-1];
if(last >= e2){
schedule.push_back(e1);
}
}
}
int last = schedule[schedule.size()-1];
if(last < e2){
schedule.push_back(e2);
schedule.push_back(e1);
}else if(e2 >= last){
schedule.push_back(e1);
}
for(int i=0;icout<}
cout<return 0;
}
#endif
avatar
h*w
92 楼
我就靠了，
各位亲们你们怎么能用sort解决！！！？？？
我给个解法吧， time complex is O(n)
建立N*31矩阵
each row element marks 1 if people available that day
EXP,
1~17 is a duration, then a[0,1] to a[0, 17] is all 1.

Of course the build time is not counted as the decision made time,
So sum every col, you got the max value (time cost O(31n)), mark
corresponding row flag value 1, till you reach a row with flag value 2, fake
delete such row, till every row is fake deleted.
How many max value you computed before all rows are faked deleted,
you find the min days to arrange the conference.
Hahaha!
avatar
r*n
93 楼
哪说了一定是同一个月之内啊....

fake

【在 h********w 的大作中提到】
: 我就靠了，
: 各位亲们你们怎么能用sort解决！！！？？？
: 我给个解法吧， time complex is O(n)
: 建立N*31矩阵
: each row element marks 1 if people available that day
: EXP,
: 1~17 is a duration, then a[0,1] to a[0, 17] is all 1.
:
: Of course the build time is not counted as the decision made time,
: So sum every col, you got the max value (time cost O(31n)), mark
avatar
h*w
94 楼
那我问你，数据是1－17，又没说1/1 to 17/1。 我理解是一个月内有什么不对？

【在 r*******n 的大作中提到】
: 哪说了一定是同一个月之内啊....
:
: fake
avatar
r*n
95 楼
你理解半个月之内也可以...总之我没体会出来.....

【在 h********w 的大作中提到】
: 那我问你，数据是1－17，又没说1/1 to 17/1。 我理解是一个月内有什么不对？
avatar
e*l
96 楼
一年也就365天，十年才3650天，一辈子也活不到30000天。认为天数最大是O(1)也无不
妥，呵呵。人数可以有十万百万什么的，比如富士康。
avatar
j*2
97 楼
哪位给个贪心法的证明吧？Note that 结果不一定是一系列离散的日期.

【在 i***h 的大作中提到】
: 你非要用集合论接当然可以
: 但是这个问题被证明排序以后有最优解
avatar
s*0
98 楼
ding

【在 j********2 的大作中提到】
: 哪位给个贪心法的证明吧？Note that 结果不一定是一系列离散的日期.
avatar
p*n
99 楼
额。。难道我理解错题意了？题里面是说组织一个event吧？而且这个event应该是连续
的？
如果是这样的话，那不就是找到最早结束的那个人，和最晚开始的那个人，然后从最早
的人结束的前一天开始，到最晚开始的人的第二天结束。
走一遍就可以了，时间是O(N),
please tell me if my understanding is wrong...
avatar
i*7
100 楼
这个是我写的代码，comment是思路
解法为贪心。
vector twodays(vector sch){
vector res;
//第一步，先按照end day排序。
sort(sch.begin(), sch.end());
//第二步，greedy algorithm.
//iteration一遍。每次选end day和 end day - 1和当前schedule对比，
//对比分两种。
//1.如果当前employee对象的start day比当前schedule的最后一个元素还要晚。
那么就直接Push当前对象end day和end day - 1.
//2.else. 表示当前schedule至少有一天可以match到employee的schedule.
//3.然后再看schedule的倒数第二个元素。如果倒数第二个元素小于当前employee
的start day。那么就表示当前employee只能match到schedule的最后一天。那么就开始
做下一个判断。
//4.如果schedule的最后一天等于当前employee的End day，那么就将schedule的
最后一天提前一天。然后再压入当前employee的最后一天。
//具体实现如下。
for(int i = 0; i < sch.size();i++){
int size = res.size();
if(size < 2 || res[size - 1] < sch[i].start)
{
res.push_back(sch[i].end - 1);
res.push_back(sch[i].end);
}
else if(res[size - 2] < sch[i].start){
if(sch[i].end == res[size - 1]){
res[size - 1]--;
}
res.push_back(sch[i].end);
}
}
return res;
}
avatar
i*7
101 楼
下面是employee的数据结构
struct employee{
public:
int start;
int end;
employee(int s, int e){start = s; end = e;}
//下面是如何重载运算符，以用于排序算法。必须要声明为常量函数，否则不通过
。。。
bool operator < (const employee& s) const{
return end < s.end;
}
bool operator == (const employee& s) const{
return end == s.end;
}
bool operator > (const employee& s) const{
return end > s.end;
}
bool operator <= (const employee& s) const{
return end <= s.end;
}
bool operator >= (const employee& s) const{
return end >= s.end;
}

};
avatar
d*0
102 楼
how about this
class employee
{
public:
int start, end;
}
int start= max, end = min;
for(int i = 0; i < employee.size();i++)
{
start=start > employee[i].end-2? employee[i].end-2:start;
end = end < employee[i].start+2? employee[i].start+2:end;
}
return (start;end)
avatar
j*2
103 楼
这个是对的，如果这个event应该是连续的。 There is one small point though:
We need to pay attention if such end – start < 1. For example, 1-5 and 2-6,
start = 4 and end = 3. When this happens, it means that when we start at
the smallest_end_day -1, everyone else already start. Thus we can just
return (smallest_end_day -1, smallest_end_day).
如果这个event不一定是连续的， Then this is a NPC. 可以转成set cover 问题。
A greedy approximation solution is first pick the day with most people being
available, remove the day and those guys then repeat till everyone gets
picked twice.

【在 p****n 的大作中提到】
: 额。。难道我理解错题意了？题里面是说组织一个event吧？而且这个event应该是连续
: 的？
: 如果是这样的话，那不就是找到最早结束的那个人，和最晚开始的那个人，然后从最早
: 的人结束的前一天开始，到最晚开始的人的第二天结束。
: 走一遍就可以了，时间是O(N),
: please tell me if my understanding is wrong...
相关阅读
借地咨询下F1的代传递业务在线申请新工作，当前工作有non-competition, non-solitation agreement请问如何在面试中show interesth1b approve到收到h1b visa要等多久？请推荐onsite报告好用的pointer知道你的权利—当遭遇执法人员时 (转载)求analyst和consultant方面职位的refer，女生！H1B Approved?美元持续走低啊HOUR stage是啥？分享一点找工作经验吧，求人品有background check fail的吗？暑期实习健康保险大家怎么弄的收到H1B退件 CA NON-PP ADV明天的eBay Seattle Open House有人面过samsung吗？有做过IT Business Relationship Manager的吗？Can I leave U.S. after received the H-1B approval notice?做contractor的问题大家说说,为什么HR有时候放求职者的鸽子？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。