由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问道难的scheduling问题
相关主题
问F家一道题一个cc150里面的题目,不解
大家帮忙看看这一道F家的题目?看看都有么有思路?收集了几个 List相关的题
一个特别的inplace merge two sorted arrayscareercup上看的一道题
有A[i]考古到一道题
昨天面试的题目问个简单的GooG题目
一个小公司面经请教suffix array的问题
问一道老题贡献两个Amazon的电话面试题
A facebook interview question哪位大写给说说 何时用 merge sort, 何时用 quick sort, 何时 heap sort
相关话题的讨论汇总
话题: days话题: algorithm话题: 参谋话题: employee话题: number
进入JobHunting版参与讨论
1 (共1页)
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
5
好,果然文如其名
g***s
发帖数: 3811
6
*步骤2需要改成如果已经参加过一次,取最后一天。否则取两天。
否则,反例 (1,2)(2,4)
* 单步步骤3不能在O(1)时间内完成。但需要证明所有第3步的总时间可以在总时
间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 的大作中提到】
: *步骤2需要改成如果已经参加过一次,取最后一天。否则取两天。
: 否则,反例 (1,2)(2,4)
: * 单步步骤3不能在O(1)时间内完成。但需要证明所有第3步的总时间可以在总时
: 间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.

1 (共1页)
进入JobHunting版参与讨论
相关主题
哪位大写给说说 何时用 merge sort, 何时用 quick sort, 何时 heap sort昨天面试的题目
CS algorithm question一个小公司面经
问道排序题问一道老题
re: 面试归来,上面经回馈各位战友A facebook interview question
问F家一道题一个cc150里面的题目,不解
大家帮忙看看这一道F家的题目?看看都有么有思路?收集了几个 List相关的题
一个特别的inplace merge two sorted arrayscareercup上看的一道题
有A[i]考古到一道题
相关话题的讨论汇总
话题: days话题: algorithm话题: 参谋话题: employee话题: number