s****t
发帖数: 220 | 1 从careercup 看到的，可能大家讨论过。不知道有没有好的解法？
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). |
f*****e
发帖数: 2992 | 2 按end 排序，和non overlapping intervals类似，取每个interval的最后一天或两天。
【在 s****t 的大作中提到】
: 从careercup 看到的，可能大家讨论过。不知道有没有好的解法？
: 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
|
j********g
发帖数: 244 | 3 同问啊 在班上见过，不过找不到了
有人能详细说说么 |
t********e
发帖数: 344 | |
t********e
发帖数: 344 | 5 想到greedy的，但是没法证明是minimum的：
1. count how many people are at work each day, and pick two days with the
maximum number of people, say D1 and D2.
2. exclude those already present twice on D1 and D2.
3. repeat 1-2 until all employee counted |
c****9
发帖数: 164 | |
c****9
发帖数: 164 | 7 如果总range一定，用bucketsort，基本上可以O（n） 每个bucket中放的是原来range
的index
【在 c****9 的大作中提到】
: 这个应该除非sort过，否则没有O（n）吧
|
R********y
发帖数: 88 | 8 这个方法应该是对的，但是做不到O(N)啊。
而且这个方法似乎连O(M)都很难做到，假定总共有M天。如果时间跨度大，比如两个员
工，第一个[1,2]，第二个[100,101]，count each day的话就太慢了。
我也是这个思路，能想到的最好的数据结构可以达到min O(NlogN),O(MN)，不知道有没
有线性的。
【在 t********e 的大作中提到】
: 想到greedy的，但是没法证明是minimum的：
: 1. count how many people are at work each day, and pick two days with the
: maximum number of people, say D1 and D2.
: 2. exclude those already present twice on D1 and D2.
: 3. repeat 1-2 until all employee counted
|
h****n
发帖数: 1093 | 9 题目就没看明白，谁能解释一下吗
真菜啊。
比如at least twice。也没说一天之内能不能参加一个event twice
【在 s****t 的大作中提到】
: 从careercup 看到的，可能大家讨论过。不知道有没有好的解法？
: 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
|
