Re: 真心求教：啥叫“美国主流社会”？ (转载) - 未名空间MITBBS历史存档

Re: 真心求教：啥叫“美国主流社会”？ (转载)# Joke - 肚皮舞运动

r*u2011-02-07 08:02

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).

d*12011-02-07 08:02

2 楼

发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
个案件的以及结果的。连同485 一起递交。
当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有
权利拒绝你，只要你材料齐全，既然法官都判你DISMISSED ，他不可能为难你。当
时我们在2个洲面试，都看了逮捕的材料， 2个面试官都没有问任何问题。
其实我的经历好多人是没有办法想像的：因为89动乱被取消出国资格后，经过近10
年才来美国，自己10多年没有学习，来美国后已经落后很多，经过7年才拿博士。其
间父亲去世没有回去。后来回去探亲，到墨西哥签证，被背景调查。差点回不来
。等了4个月才拿到签证。（虽然被逮捕过，也没有担心）。背景调查我以前去过
穆斯林国家工作过。
7年毕业的时候，文章少，根本不可能做波后。老板临时改变主意，不许毕业，但
已经通知国际办公室那学期毕业。结果造成I-20 过期，后来找理由，国际办公室给
移民局解释，然后同意我2月答辩（老板虽然反对，但他没有办法，只好同意我毕
业。 3月自己花1000美元去面试工作。给32000。当时儿子在电话里说“爸爸，接，
接。你们如果回中国，我怎么办呢？” 孩子的哭腔声，我现在都记得。
孩子成绩很好，可因为没有卡，不够资格得到NATIONAL MERIT SCHOLARSHIP。对孩子
的心灵伤害很大。感谢神，原本因为我们得付洲外学费的，结果学校来信主动免洲
外学费，还给了部分奖学金。。
后来找到现在的工作。虽然起点低，但行业就这样，到现在还是很被重用的。
题外话：关于主。因为我信主。很多事情我只能用主才可以解释。所以大家别为这
争论了。让自己去感觉吧。

d*f2011-02-07 08:02

3 楼

【以下文字转载自 Military 讨论区】
发信人: fish99 (DT), 信区: Military
标题: Re: 真心求教：啥叫“美国主流社会”？
发信站: BBS 未名空间站 (Sun Feb 6 22:00:40 2011, 美东)
主流社会就是蹲马桶时把裤子褪到地上。你进入主流社会了吗？
长。

x*o2011-02-07 08:02

4 楼

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 Bplease 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).

m*k2011-02-07 08:02

5 楼

占个沙发

r*y2011-02-07 08:02

6 楼

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

s*G2011-02-07 08:02

7 楼

jeez.... bless

O*n2011-02-07 08:02

8 楼

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

t*l2011-02-07 08:02

9 楼

是这样啊！我原来一直觉得dream说话不好听，基本是看到你发帖就绕道走的。今天才
知道你们的这趟这么不容易。不过想想小孩这么让你们省心。很不错啊。

O*n2011-02-07 08:02

10 楼

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

o*t2011-02-07 08:02

11 楼

真不容易。一切事在人为。我个人的经历是只有自己才能掌握自己的命运。
MD 搞笑的地方就是64的参与者反而在煎熬绿卡。

x*o2011-02-07 08:02

12 楼

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

d*12011-02-07 08:02

13 楼

这世界很滑稽吧？

【在 o******t 的大作中提到】

: 真不容易。一切事在人为。我个人的经历是只有自己才能掌握自己的命运。
: MD 搞笑的地方就是64的参与者反而在煎熬绿卡。

c*e2011-02-07 08:02

14 楼

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)

i*d2011-02-07 08:02

15 楼

苦尽甘来。能感恩能珍惜就好。恭喜。

m*l2011-02-07 08:02

16 楼

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).

m*t2011-02-07 08:02

17 楼

真不容易
我当年还翻过dreamer的老帖，惭愧惭愧。

f*w2011-02-07 08:02

18 楼

我觉得"attend twice" 的定义不是特别明确

q*c2011-02-07 08:02

19 楼

感动，顶，赞!

g*i2011-02-07 08:02

20 楼

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).

m*l2011-02-07 08:02

21 楼

为什么用衣架?

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

f*g2011-02-07 08:02

22 楼

如果要求员工只参加一次，这肯定是greedy的。
先按照员工时间排序，在第一个结束的天放一个event，然后去掉那些能够覆盖着一天
的员工，继续找下一个结束点。
如果要求参加两次，我觉得也是greedy的。
待求证

f*i2011-02-07 08:02

23 楼

真的很谢谢你。这条路大家走得都很辛苦，而且现在连U-turn都不可能了。大家继续共
勉。

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

m*l2011-02-07 08:02

24 楼

我想了下， greedy不太行：
6个工人
1，2
1，2
1，2
1，3
3, 4
3, 5

【在 f***g 的大作中提到】

: 如果要求员工只参加一次，这肯定是greedy的。
: 先按照员工时间排序，在第一个结束的天放一个event，然后去掉那些能够覆盖着一天
: 的员工，继续找下一个结束点。
: 如果要求参加两次，我觉得也是greedy的。
: 待求证

m*l2011-02-07 08:02

25 楼

你的经历确实值得叹息一声.

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

d*l2011-02-07 08:02

26 楼

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。也就是不存在满足不了的人。

m*l2011-02-07 08:02

27 楼

在叹一声,觉得有些事该回国还是该,这个会遗憾一辈子

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

l*g2011-02-07 08:02

28 楼

可不可以用下面的算法？借鉴了前面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

y*02011-02-07 08:02

29 楼

不容易。

t*y2011-02-07 08:02

30 楼

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)

l*n2011-02-07 08:02

31 楼

老战友，恭喜你终于如愿以偿。所有过去都可以成为历史，不用再担心了

p*r2011-02-07 08:02

32 楼

这是曾经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).

c*n2011-02-07 08:02

33 楼

几分唏嘘。。顶你。

d*l2011-02-07 08:02

34 楼

有这么复杂？线段树非常强大，但用在这题上不是很顺吧。我在前面的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

c*62011-02-07 08:02

35 楼

真不容易

f*y2011-02-07 08:02

36 楼

唉，题目没有看懂。。

【在 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).

a*x2011-02-07 08:02

37 楼

主最喜欢这样的了。

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

R*d2011-02-07 08:02

38 楼

ding

S*t2011-02-07 08:02

39 楼

苦尽甘来。你儿子这么有出息，也很不容易！这么多年的曲折，造就了你强大的内心和
豁达的态度，相信对你而言没有什么过不去的坎了。

c*02011-02-07 08:02

40 楼

难道这个不是set cover问题吗？ greedy肯定不是最优解吧

r*u2011-02-07 08:02

41 楼

不容易
祝福

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

g*s2011-02-07 08:02

42 楼

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*l2011-02-07 08:02

43 楼

God bless you.

c*y2011-02-07 08:02

44 楼

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.

l*n2011-02-07 08:02

45 楼

真心祝福lz

g*s2011-02-07 08:02

46 楼

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?

a*e2011-02-07 08:02

47 楼

C'est la vie

【在 o******t 的大作中提到】

: 真不容易。一切事在人为。我个人的经历是只有自己才能掌握自己的命运。
: MD 搞笑的地方就是64的参与者反而在煎熬绿卡。

d*l2011-02-07 08:02

48 楼

这题的event到底必须是连续的还是可以是离散的？

s*92011-02-07 08:02

49 楼

big bless

g*s2011-02-07 08:02

50 楼

It should be 离散的. Otherwise it is a very simple question. I think the lz
gave wrong/un-cleared description.

【在 d*******l 的大作中提到】

: 这题的event到底必须是连续的还是可以是离散的？

f*e2011-02-07 08:02

51 楼

Congrs!
挺不容易的！

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

c*y2011-02-07 08:02

52 楼

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;

p*e2011-02-07 08:02

53 楼

苦尽甘来, god bless you.......not easy to you and your family

g*s2011-02-07 08:02

54 楼

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

a*o2011-02-07 08:02

55 楼

是教训孩子，又不是要打伤他。衣架趁便，又不重。如果用椅子砸，估计三级重罪就无
法dismiss了。

【在 m*******l 的大作中提到】

: 为什么用衣架?

c*y2011-02-07 08:02

56 楼

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

S*t2011-02-07 08:02

57 楼

bless

g*s2011-02-07 08:02

58 楼

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.

B*g2011-02-07 08:02

59 楼

原创？

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

c*y2011-02-07 08:02

60 楼

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;

f*n2011-02-07 08:02

61 楼

dream 321来了个苦肉计

【在 B*****g 的大作中提到】

: 原创？

m*i2011-02-07 08:02

62 楼

What are nonepointset and onepointset.
Could you explain them.

b*k2011-02-07 08:02

63 楼

好曲折。。。现在好了。祝幸福。

g*s2011-02-07 08:02

64 楼

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?

t*42011-02-07 08:02

65 楼

Blessing!
有件事楼主可能没做好： NATIONAL MERIT SCHOLARSHIP是不需要Gc的，AOS就够了，我
小孩就是凭AOS拿的， look carefully about the instruction.

g*e2011-02-07 08:02

66 楼

我觉得这题有两种理解，举个例子
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)

A*s2011-02-07 08:02

67 楼

Cong

g*s2011-02-07 08:02

68 楼

nonepointset: 所有不包含event的线段集合（到目前为止）
onepointset: 所有包含一个event的线段集合（到目前为止）

【在 m****i 的大作中提到】

: What are nonepointset and onepointset.
: Could you explain them.

w*62011-02-07 08:02

69 楼

big cong!
you're greened finally

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

g*s2011-02-07 08:02

70 楼

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应该可以解

f*t2011-02-07 08:02

71 楼

一声叹息，楼主苦尽甘来。

s*y2011-02-07 08:02

72 楼

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应该可以解

f*t2011-02-07 08:02

73 楼

一声叹息，楼主苦尽甘来。

d*l2011-02-07 08:02

74 楼

其实我对这题的理解一直是event必须是连续的若干天，我们要使event的天数尽量少，
并且保证每个人都能够找出两天参加。这样只要算开始和结束日期的上界和下界应该就
可以，不知道这算不算greedy

e*t2011-02-07 08:02

75 楼

祝贺你拿到绿卡，但是拿衣架打孩子还是不可接受的，现在你孩子大了想必你已经不这
么做了。我小时候我父亲也是，一旦孩子不听话就打，对我们的伤害很大，我母亲后来
总是说因为文革耽误了，事业上不那么顺利心情不好，对我们的期待就高，现在回想，
只有懦夫才会拿无力反抗的孩子出气，无能的人才会用暴力来解决问题。

g*s2011-02-07 08:02

76 楼

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得是最优啊？

r*02011-02-07 08:02

77 楼

Bless & Cong!!!

s*y2011-02-07 08:02

78 楼

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)

t*o2011-02-07 08:02

79 楼

God bless you

g*s2011-02-07 08:02

80 楼

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?

j*e2011-02-07 08:02

81 楼

祝福你。

s*y2011-02-07 08:02

82 楼

你的算法里面
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

m*92011-02-07 08:02

83 楼

很令人感动的经历，我想只有楼主才能切身体会到其中的辛苦和从容。
Thanks Lord

s*y2011-02-07 08:02

84 楼

你的算法里面
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

l*p2011-02-07 08:02

85 楼

祝福~

g*s2011-02-07 08:02

86 楼

Scan all points of the segments.
Sets store segments.

【在 s*****y 的大作中提到】

: 你的算法里面
: set里面存的是点，还是segment，譬如1-4 4-6 你存的是4的这个点，还是4-6这个
: range啊？对point和segment有点confuse。

g*g2011-02-07 08:02

87 楼

你信的这个主也够操蛋的。

s*y2011-02-07 08:02

88 楼

看来我理解错了
那么这一步：
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.

r*c2011-02-07 08:02

89 楼

jeez, 不容易啊，哥们，必有后福

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

g*s2011-02-07 08:02

90 楼

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不只是起始，结束点？而是起始+结束+他们直接的点？

p*e2011-02-07 08:02

91 楼

为弟兄祈祷！

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

s*y2011-02-07 08:02

92 楼

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

w*r2011-02-07 08:02

93 楼

God Bless!

m*p2011-02-07 08:02

94 楼

拨开云雾见青天
精诚所至金石为开
祝福楼主！

发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。我孩
子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现孩子
手臂上明显的3条衣........

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

b*n2011-02-07 08:02

95 楼

Congratulations and bless

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

s*e2011-02-07 08:02

96 楼

God bless you!

x*c2011-02-07 08:02

97 楼

大家都不容易，祝福你好运！

m*n2011-02-07 08:02

98 楼

有没有 criminal record?

y*r2011-02-07 08:02

99 楼

dreamer321,祝福你，一路走来真不容易啊。

s*y2011-02-07 08:02

100 楼

拨云见日。好

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

G*o2011-02-07 08:02

101 楼

wow

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

l*i2011-02-07 08:02

102 楼

感谢主

【在 d********1 的大作中提到】

: 发帖简单谈了下经历，很多人发信问我关于逮捕的问提，在这里给大家说说。
: 我孩子在我来后半年来的。用衣架打的孩子，隔壁白人报案， 3名警察来后，发现
: 孩子手臂上明显的3条衣架痕迹， 2名警察说是文化问题，一名坚持要逮捕我。没有钱
: ，只能找政府提供的免费律师。 THIRD FELONY---就是我的罪名。前后2次上庭，最
: 后案件被DISMISS 了。很多人有夫妻吵架，打孩子，商店无意带东西出来等被逮捕
: 。最后都不可能到我这级罪名的。当然最关键的是，最后如何定罪的问题。我以上
: 提的这些情况，哪怕就找免费的律师，他和法官沟通后，最后的结果都应该是
: DISMISSED 的。最后交485 的时候应该到当时的DISTRICT COURT 要个文件，纪录整
: 个案件的以及结果的。连同485 一起递交。
: 当然面谈是肯定了。可面试的移民官员根本对这些不理睬的。他们不是法官，没有

v*o2011-02-07 08:02

103 楼

感谢主