r*********u
发帖数: 75 | 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). |
x********o
发帖数: 519 | 2 find the max of the first date, and min of the second date, say they are A
and B respectively.
if B>=A, choose A, A+1
if B
please correct me if I am wrong
【在 r*********u 的大作中提到】
: 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).
|
r*******y
发帖数: 1081 | 3 try this one
1-3
5-7
9-11
then A = 9
B =3
But [B-1, A+1] is not minimum days
【在 x********o 的大作中提到】
: find the max of the first date, and min of the second date, say they are A
: and B respectively.
: if B>=A, choose A, A+1
: if B: please correct me if I am wrong
|
O******n
发帖数: 1505 | 4
1-3
3-5
2-2
3-3
an
is
【在 x********o 的大作中提到】
: find the max of the first date, and min of the second date, say they are A
: and B respectively.
: if B>=A, choose A, A+1
: if B: please correct me if I am wrong
|
O******n
发帖数: 1505 | 5 what's the obvious O(N) solution?
cause I cant imagine one...
【在 r*******y 的大作中提到】
: try this one
: 1-3
: 5-7
: 9-11
: then A = 9
: B =3
: But [B-1, A+1] is not minimum days
|
x********o
发帖数: 519 | 6 you are right.
then what's the O(n) algo?
must be implemented in an elegant way.
【在 r*******y 的大作中提到】
: try this one
: 1-3
: 5-7
: 9-11
: then A = 9
: B =3
: But [B-1, A+1] is not minimum days
|
c******e
发帖数: 73 | 7 could sort based on the end date of each person o(nlogN) and then scan one
time O(n) from the end first people to get the result.
It will be nLogn to sort the data. Not sure the way for for O(n) |
m********l
发帖数: 4394 | 8 0) define 3 sets. Date (all possible dates), PeopleRemainOne,
PeopleRemainTwo.
1) find a date from Date. The date is when most people in
PeopleRemainOne are in
2) remove the date from Date set. Remove people from PeopleRemainOne
3) find a date from Date. The date is when most people in
PeopleRemainTwo are in.
4) remove the date from Date Set. Remove people from PeopleRemainTwo.
5) repeat 1)-4) until both PeopleRemainOne and PeopleRemainTwo are
empty.
an
(there is
【在 r*********u 的大作中提到】
: 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*****w
发帖数: 2602 | 9 我觉得"attend twice" 的定义不是特别明确 |
g*****i
发帖数: 2162 | 10 event是连续的还是可以离散的?
【在 r*********u 的大作中提到】
: 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***g
发帖数: 214 | 11 如果要求员工只参加一次，这肯定是greedy的。
先按照员工时间排序，在第一个结束的天放一个event，然后去掉那些能够覆盖着一天
的员工，继续找下一个结束点。
如果要求参加两次，我觉得也是greedy的。
待求证 |
m********l
发帖数: 4394 | 12 我想了下， greedy不太行：
6个工人
1，2
1，2
1，2
1，3
3, 4
3, 5
【在 f***g 的大作中提到】
: 如果要求员工只参加一次，这肯定是greedy的。
: 先按照员工时间排序，在第一个结束的天放一个event，然后去掉那些能够覆盖着一天
: 的员工，继续找下一个结束点。
: 如果要求参加两次，我觉得也是greedy的。
: 待求证
|
d*******l
发帖数: 338 | 13 minE = -INF
maxS = INF
foreach (s, e)
minE = max(minE, s+1)
maxS = min(maxS, e-1)
if(minE > maxS)
return (maxS, minE)
return (maxS, maxS+1）
默认对于每对(s, e)，e至少比s大1。也就是不存在满足不了的人。 |
l*****g
发帖数: 685 | 14 可不可以用下面的算法？借鉴了前面mercuriusl的思路
1）所有工人在original set setA里; create setB 用来存放已经找到one date的工人
2）create a set resultDates 用于存放找到的dates
3）用个sorted dictionary datePersonCounts统计出每天overlap
的人数
接下去就做以下循环：
4）从datePersonCounts中选择overlap人数最多的一天，maxDate，把它放进
resultDates，然后把dictionary中maxDate对应的entry删除
5) 在setB中找出maxDate那天available的工人，把他从setB删除；同时把工人的
available range中的所有dates, 从dictionary中减去：
datePersonCounts[date] -= 1;
6）在setA中找maxDate那天available的工人, 把他们从setA move to setB
（4）-（6）循环，直到setA和setB皆为空。
我证明不了结果对不对。但思路也是greedy，因为每次循环都选择overlap最多的那一天
（ 跟fzblg的greedy不一样）
因为基本操作是把dictionary每一天的personCount累加，然后又逐渐减去最后至0；所
以复杂度可以表达成
O(D1 + D2 + ... + Dn) (Di 是 person Pi available的天数）
简化一下，取d 为其中最大的Di。那么复杂度是 O(dn), 也就是O(n)
【在 m********l 的大作中提到】
: 我想了下， greedy不太行：
: 6个工人
: 1，2
: 1，2
: 1，2
: 1，3
: 3, 4
: 3, 5
|
t******y
发帖数: 884 | 15 You can do it as follows:
1. O(n)
1.1 for i = 0 .. n-2
1.2 compare interval[i] and interval[i-1], consider (intersection, no
intersection) cases, to find the (min_l, min_h)
1.3 return the final interval
2. use a variant of interval tree algorithm
to preprocess the data as interval tree ordered by lower bound of each
interval, and store additional field to hold the minimum date(start, end) of
its subtrees of each node.
then the time is O(1) (get value from root).
For each node insertion, it takes O(logn) |
p*****r
发帖数: 1883 | 16 这是曾经MSRA中国的面试题，参看《编程之美》，解法是用DP，或者是线段树 segment tree
【在 r*********u 的大作中提到】
: 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).
|
d*******l
发帖数: 338 | 17 有这么复杂？线段树非常强大，但用在这题上不是很顺吧。我在前面的post里提到一个
简单的O(n)的做法，我觉得好像是没错的。再写一次：
minE = -INF
maxS = INF
foreach (s, e)
minE = max(minE, s+1)
maxS = min(maxS, e-1)
if(minE > maxS)
return (maxS, minE)
return (maxS, maxS+1）
segment tree
【在 p*****r 的大作中提到】
: 这是曾经MSRA中国的面试题，参看《编程之美》，解法是用DP，或者是线段树 segment tree
|
f*****y
发帖数: 444 | 18 唉，题目没有看懂。。
【在 r*********u 的大作中提到】
: 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).
|
R*******d
发帖数: 13640 | |
c********0
发帖数: 112 | 20 难道这个不是set cover问题吗？ greedy肯定不是最优解吧 |
|
|
g***s
发帖数: 3811 | 21 we discussed this question a few months ago.
the number of people is n and num of days is m. m<
algo using count-sort and greedy. |
c***y
发帖数: 560 | 22 more detail, please, how could we conver this problem to that one?
【在 g***s 的大作中提到】
: we discussed this question a few months ago.
: the number of people is n and num of days is m. m<: algo using count-sort and greedy.
|
g***s
发帖数: 3811 | 23 1. sort all points (begin and end)
2. for (point x: all points smallest to largest)
3. if (x is a begin point)
add the segment of x into NonePointSet
4. else { // x is a end point
5 if (x is in the NonePointSet) {
6 set two events on day x;
7 clear NonePointSet & OnePointSet;
8 } else { x is in the OnePointSet) {
9 set one event on day x;
10 OnePointSet.addAll(NonePointSet);
11 clear NonePointSet
12 } // else the segment of x is already has two events
13 }
1 is O(n) using couting sort
2-13 is O(n)
【在 c***y 的大作中提到】
: more detail, please, how could we conver this problem to that one?
|
d*******l
发帖数: 338 | 24 这题的event到底必须是连续的还是可以是离散的？ |
g***s
发帖数: 3811 | 25 It should be 离散的. Otherwise it is a very simple question. I think the lz
gave wrong/un-cleared description.
【在 d*******l 的大作中提到】
: 这题的event到底必须是连续的还是可以是离散的？
|
c***y
发帖数: 560 | 26 one question, the points only include start and begin of a person?
for example, person 1-4, only include 1,4 as the points, or include 1,2,3,4?
thanks
【在 g***s 的大作中提到】
: 1. sort all points (begin and end)
: 2. for (point x: all points smallest to largest)
: 3. if (x is a begin point)
: add the segment of x into NonePointSet
: 4. else { // x is a end point
: 5 if (x is in the NonePointSet) {
: 6 set two events on day x;
: 7 clear NonePointSet & OnePointSet;
: 8 } else { x is in the OnePointSet) {
: 9 set one event on day x;
|
g***s
发帖数: 3811 | 27 1 4 only
【在 c***y 的大作中提到】
: one question, the points only include start and begin of a person?
: for example, person 1-4, only include 1,4 as the points, or include 1,2,3,4?
: thanks
|
c***y
发帖数: 560 | 28 say person1: 1-4, person2: 2-5, person3: 4-6
using your approach to do sort first
1(p1) 2(p2) 4(p3) 4(p1) 5(p2) 6(p3)
how can you figure it out it's days 2 4 6 or 3 4 6? thanks.
【在 g***s 的大作中提到】
: 1 4 only
|
g***s
发帖数: 3811 | 29 two events in day 4 is the solution
【在 c***y 的大作中提到】
: say person1: 1-4, person2: 2-5, person3: 4-6
: using your approach to do sort first
: 1(p1) 2(p2) 4(p3) 4(p1) 5(p2) 6(p3)
: how can you figure it out it's days 2 4 6 or 3 4 6? thanks.
|
c***y
发帖数: 560 | 30
For 1-4, when coming to 4, what does this x mean, meaning 1-4, or
4 itself?
【在 g***s 的大作中提到】
: 1. sort all points (begin and end)
: 2. for (point x: all points smallest to largest)
: 3. if (x is a begin point)
: add the segment of x into NonePointSet
: 4. else { // x is a end point
: 5 if (x is in the NonePointSet) {
: 6 set two events on day x;
: 7 clear NonePointSet & OnePointSet;
: 8 } else { x is in the OnePointSet) {
: 9 set one event on day x;
|
|
|
m****i
发帖数: 650 | 31 What are nonepointset and onepointset.
Could you explain them. |
g***s
发帖数: 3811 | 32 x=4(p3) then x=4(p1)
【在 c***y 的大作中提到】
:
: For 1-4, when coming to 4, what does this x mean, meaning 1-4, or
: 4 itself?
|
g**e
发帖数: 6127 | 33 我觉得这题有两种理解，举个例子
1. 两个seminar，每个一小时比如。两个可以在同一天举行。每个人必须两个都参加一
遍。1－4这种范围表示这个人在第一天到第四天任何时间里都可以参加任何一个。你的
解法是针对这种理解。所以如果有1-4, 2-5, 4-6，最佳结果是第四天同时举行两个
seminar。
2. 只有一个seminar，持续一整天。每个人必须参加两次。也就是说举行seminar的天
数最少是两天。那么同样的1-4, 2-5, 4-6，最后的结果是3-5共举行3天。不少同学似
乎是这么理解的，我也是…… 这种情况greedy应该可以解
【在 g***s 的大作中提到】
: x=4(p3) then x=4(p1)
|
g***s
发帖数: 3811 | 34 nonepointset: 所有不包含event的线段集合（到目前为止）
onepointset: 所有包含一个event的线段集合（到目前为止）
【在 m****i 的大作中提到】
: What are nonepointset and onepointset.
: Could you explain them.
|
g***s
发帖数: 3811 | 35 2. 可以类似的思路。但需要稍微改一些，比1要麻烦一些。
【在 g**e 的大作中提到】
: 我觉得这题有两种理解，举个例子
: 1. 两个seminar，每个一小时比如。两个可以在同一天举行。每个人必须两个都参加一
: 遍。1－4这种范围表示这个人在第一天到第四天任何时间里都可以参加任何一个。你的
: 解法是针对这种理解。所以如果有1-4, 2-5, 4-6，最佳结果是第四天同时举行两个
: seminar。
: 2. 只有一个seminar，持续一整天。每个人必须参加两次。也就是说举行seminar的天
: 数最少是两天。那么同样的1-4, 2-5, 4-6，最后的结果是3-5共举行3天。不少同学似
: 乎是这么理解的，我也是…… 这种情况greedy应该可以解
|
s*****y
发帖数: 897 | 36 greddy的话怎么解，怎么证明greeddy得是最优啊？
【在 g**e 的大作中提到】
: 我觉得这题有两种理解，举个例子
: 1. 两个seminar，每个一小时比如。两个可以在同一天举行。每个人必须两个都参加一
: 遍。1－4这种范围表示这个人在第一天到第四天任何时间里都可以参加任何一个。你的
: 解法是针对这种理解。所以如果有1-4, 2-5, 4-6，最佳结果是第四天同时举行两个
: seminar。
: 2. 只有一个seminar，持续一整天。每个人必须参加两次。也就是说举行seminar的天
: 数最少是两天。那么同样的1-4, 2-5, 4-6，最后的结果是3-5共举行3天。不少同学似
: 乎是这么理解的，我也是…… 这种情况greedy应该可以解
|
d*******l
发帖数: 338 | 37 其实我对这题的理解一直是event必须是连续的若干天，我们要使event的天数尽量少，
并且保证每个人都能够找出两天参加。这样只要算开始和结束日期的上界和下界应该就
可以，不知道这算不算greedy |
g***s
发帖数: 3811 | 38 change steps 6,7 to:
6 set one event on day x; set one event on day x-1;
7.1 clear OnePointSet; clear NonePointSet;
7.2 add all segments that start_points = x OnePointSet; (these are
the last elements in NonePointSet before 7.1)
【在 s*****y 的大作中提到】
: greddy的话怎么解，怎么证明greeddy得是最优啊？
|
s*****y
发帖数: 897 | 39 Hi, grass
so this update solution is still base on the assumption that 2 events could
happen on same day?
【在 g***s 的大作中提到】
: change steps 6,7 to:
: 6 set one event on day x; set one event on day x-1;
: 7.1 clear OnePointSet; clear NonePointSet;
: 7.2 add all segments that start_points = x OnePointSet; (these are
: the last elements in NonePointSet before 7.1)
|
g***s
发帖数: 3811 | 40 No. one day can only have one event. but i assume all end-i > start-j:
nobody comes and leaves at same day.
could
【在 s*****y 的大作中提到】
: Hi, grass
: so this update solution is still base on the assumption that 2 events could
: happen on same day?
|
|
|
s*****y
发帖数: 897 | 41 你的算法里面
set里面存的是点，还是segment，譬如1-4 4-6 你存的是4的这个点，还是4-6这个
range啊？ 对point和segment有点confuse。
【在 g***s 的大作中提到】
: No. one day can only have one event. but i assume all end-i > start-j:
: nobody comes and leaves at same day.
:
: could
|
s*****y
发帖数: 897 | 42 你的算法里面
set里面存的是点，还是segment，譬如1-4 4-6 你存的是4的这个点，还是4-6这个
range啊？ 对point和segment有点confuse。
【在 g***s 的大作中提到】
: No. one day can only have one event. but i assume all end-i > start-j:
: nobody comes and leaves at same day.
:
: could
|
g***s
发帖数: 3811 | 43 Scan all points of the segments.
Sets store segments.
【在 s*****y 的大作中提到】
: 你的算法里面
: set里面存的是点，还是segment，譬如1-4 4-6 你存的是4的这个点，还是4-6这个
: range啊？ 对point和segment有点confuse。
|
s*****y
发帖数: 897 | 44 看来我理解错了
那么这一步：
1. sort all points (begin and end)
2. for (point x: all points smallest to largest)
你的point不只是起始，结束点？ 而是起始+结束+他们直接的点？
【在 g***s 的大作中提到】
: Scan all points of the segments.
: Sets store segments.
|
g***s
发帖数: 3811 | 45 only start points + end points
p1 1-4
p2 3-5
p3 4-7
x will be 1,3,4(p3),4(p1),5,7
when x=4(p1), it add event on day 3 and day 4
p3 will be put in OnePointSet
x=5 do nothing since p2 is not in both set
x=7 add event on day 7 since p3 is in OnePointSet
set, solution is 3, 4, 7
【在 s*****y 的大作中提到】
: 看来我理解错了
: 那么这一步：
: 1. sort all points (begin and end)
: 2. for (point x: all points smallest to largest)
: 你的point不只是起始，结束点？ 而是起始+结束+他们直接的点？
|
s*****y
发帖数: 897 | 46 thanks very much. Now I understand.
【在 g***s 的大作中提到】
: only start points + end points
: p1 1-4
: p2 3-5
: p3 4-7
: x will be 1,3,4(p3),4(p1),5,7
: when x=4(p1), it add event on day 3 and day 4
: p3 will be put in OnePointSet
: x=5 do nothing since p2 is not in both set
: x=7 add event on day 7 since p3 is in OnePointSet
: set, solution is 3, 4, 7
|
