v******y
发帖数: 22 | 1 FB的，想不出好算法,大家参谋参谋?
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). | j********x
发帖数: 2330 | 2 O n :
For each person schedule two days on the most overlapped days, continue
until all ppl are scheduled.
I doubt there is o n solution. Since knowing the overlap of ppl is o n
square or o number of days.
The correctness is not given I don't have a clue yet. | v******y
发帖数: 22 | 3 You solution Looks good, thanks, though the correctness is not clear to me
neither. | b***e
发帖数: 1419 | 4 Roughly
1. 按终点排序。
2. 第一个终点前的最后两天。
3. 干掉所有已经参加两次的，标志所有参加了一次的。
4. goto 2
排完序就是O(n).
an
(there is
【在 v******y 的大作中提到】
: FB的，想不出好算法,大家参谋参谋?
: 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
| v******y
发帖数: 22 | | g***s
发帖数: 3811 | 6 ＊步骤２需要改成如果已经参加过一次，取最后一天。否则取两天。
否则，反例 （１，２）（２，４）
* 单步步骤３不能在O（１）时间内完成。但需要证明所有第３步的总时间可以在总时
间O（n）时间内
完成(具体算法也稍微麻烦一些)。
不过，既然排序已经用了O（nlgn），这里单步简单的用O（lgn）也就行了。总时间
反正都是O
（nlgn）.
除非，参加的人数n＞＞总天数。那么，可以找到排序的算法是O（n）。那么这题总时
间复杂度才可能是
O（n）
【在 b***e 的大作中提到】
: Roughly
: 1. 按终点排序。
: 2. 第一个终点前的最后两天。
: 3. 干掉所有已经参加两次的，标志所有参加了一次的。
: 4. goto 2
: 排完序就是O(n).
:
: an
: (there is
| b***e
发帖数: 1419 | 7 Agree for step2. But I said roughly, and I was lazy.
Don't agree for the n*log(n) argument because:
1. If the problem input is already sorted, what would you do?
2. More importantly, we are the best kind, and we only do the best.
【在 g***s 的大作中提到】
: ＊步骤２需要改成如果已经参加过一次，取最后一天。否则取两天。
: 否则，反例 （１，２）（２，４）
: * 单步步骤３不能在O（１）时间内完成。但需要证明所有第３步的总时间可以在总时
: 间O（n）时间内
: 完成(具体算法也稍微麻烦一些)。
: 不过，既然排序已经用了O（nlgn），这里单步简单的用O（lgn）也就行了。总时间
: 反正都是O
: （nlgn）.
: 除非，参加的人数n＞＞总天数。那么，可以找到排序的算法是O（n）。那么这题总时
: 间复杂度才可能是
| g***s
发帖数: 3811 | 8 For step 3), i think we also need a sorted list by first day. otherwise,
how to get O(n) cost for step (3)?
And i think another question hiding in this question is:
When day number is much less the person number, we can sort them by O(n).
It is very common for a meeting: e.g. 10k people, in 20 days.
【在 b***e 的大作中提到】
: Agree for step2. But I said roughly, and I was lazy.
: Don't agree for the n*log(n) argument because:
: 1. If the problem input is already sorted, what would you do?
: 2. More importantly, we are the best kind, and we only do the best.
|
|
|
