us airways的卡要會自動換成巴克萊的aa了 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

us airways的卡要會自動換成巴克萊的aa了

us airways的卡要會自動換成巴克萊的aa了# Money - 海外理财

g*y2014-04-07 07:04

1 楼

就不说哪些公司的了，签了NDA怕有麻烦。其中两道挺有意思的。
1. give a list of events in the following structure. Set the conflict flag
to true if the event conflicts with any other event in the list.
class Event
{
int start;
int end;
bool conflict;
}
2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序
的。输出这个国家的语言的字母顺序。

b*k2014-04-07 07:04

2 楼

citi家的酒店和航空卡怎麼都成了和其他銀行共享的
或者CITI不再發行AA ？

l*a2014-04-07 07:04

3 楼

你们单位那么好，怎么都跑出来面试

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

: 就不说哪些公司的了，签了NDA怕有麻烦。其中两道挺有意思的。
: 1. give a list of events in the following structure. Set the conflict flag
: to true if the event conflicts with any other event in the list.
: class Event
: {
: int start;
: int end;
: bool conflict;
: }
: 2. 给你一本其他国家语言的字典。其中的单词是按照这个国家的语言的字母顺序排序

d*02014-04-07 07:04

4 楼

每年一万点还有吗？

【在 b*****k 的大作中提到】

: citi家的酒店和航空卡怎麼都成了和其他銀行共享的
: 或者CITI不再發行AA ？

b*e2014-04-07 07:04

5 楼

第一题interval tree可以做。
第二题先根据字母顺序关系建有向图，然后用topological sorting。不知道有没有更
简单的办法。

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

y*i2014-04-07 07:04

6 楼

new AA cards, after the merge of the frequent flyer programs, will be
exclusively issued by Citi

【在 b*****k 的大作中提到】

: citi家的酒店和航空卡怎麼都成了和其他銀行共享的
: 或者CITI不再發行AA ？

l*b2014-04-07 07:04

7 楼

第二个和昨天的部分比较排序类似？

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

b*k2014-04-07 07:04

8 楼

圖片顯示的這張是臨時性卡？

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

: new AA cards, after the merge of the frequent flyer programs, will be
: exclusively issued by Citi

e*e2014-04-07 07:04

9 楼

Just my 2 cents.
1. Build an interval tree. for each event, check if its start and end are in
direct parent-child relationship. If yes, no conflict for this event.
2. Use a java.util.TreeSet.
for each entry in dict
treeSet.add(entry.firstCharacter).
print out treeSet.

x*i2014-04-07 07:04

10 楼

Not any more...

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

: 每年一万点还有吗？

b*e2014-04-07 07:04

11 楼

光看每一个词的第一个字符不能保证字符集的完整性吧。

in

【在 e****e 的大作中提到】

: Just my 2 cents.
: 1. Build an interval tree. for each event, check if its start and end are in
: direct parent-child relationship. If yes, no conflict for this event.
: 2. Use a java.util.TreeSet.
: for each entry in dict
: treeSet.add(entry.firstCharacter).
: print out treeSet.

y*i2014-04-07 07:04

12 楼

hard to say how long Barclaycard is willing to hold on to this portfolio
since they can't take in new applicants after the merge, the number of cards
they serve can only go down, so at certain point, they may just cut it
loose.

【在 b*****k 的大作中提到】

:
: 圖片顯示的這張是臨時性卡？

l*b2014-04-07 07:04

13 楼

万一有的字母不做开头怎么办

in

【在 e****e 的大作中提到】

i*t2014-04-07 07:04

14 楼

Do you mean we need to apply this card right now before Barclay can't take
in new applicants? Thanks!

cards

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

: hard to say how long Barclaycard is willing to hold on to this portfolio
: since they can't take in new applicants after the merge, the number of cards
: they serve can only go down, so at certain point, they may just cut it
: loose.

l*a2014-04-07 07:04

15 楼

in
2.
abc
acc
bbc

【在 e****e 的大作中提到】

c*n2014-04-07 07:04

16 楼

已经有的卡转成AA
新发行的AA卡只有citi才能做
也就说barclay的客户越来越少

【在 b*****k 的大作中提到】

: citi家的酒店和航空卡怎麼都成了和其他銀行共享的
: 或者CITI不再發行AA ？

g*y2014-04-07 07:04

17 楼

你咋知道我是哪个厂的。。。。

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

: 你们单位那么好，怎么都跑出来面试

y*i2014-04-07 07:04

18 楼

that's what I plan to do
have been churning this card every 6 months or so for the past two years
the current best offer is 40,000 miles after 1st purchase with $89 annual
fee, they often offer 15,000 miles for spending $500 each month for 3 months
, so overall not a bad deal

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

: Do you mean we need to apply this card right now before Barclay can't take
: in new applicants? Thanks!
:
: cards

g*y2014-04-07 07:04

19 楼

具体说说怎么根据字母顺序建图？难点在这里。

【在 b****e 的大作中提到】

: 第一题interval tree可以做。
: 第二题先根据字母顺序关系建有向图，然后用topological sorting。不知道有没有更
: 简单的办法。

f*i2014-04-07 07:04

20 楼

每张卡都有每年的10k miles吗？

months

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

: that's what I plan to do
: have been churning this card every 6 months or so for the past two years
: the current best offer is 40,000 miles after 1st purchase with $89 annual
: fee, they often offer 15,000 miles for spending $500 each month for 3 months
: , so overall not a bad deal

g*y2014-04-07 07:04

21 楼

不太了解interval tree。说说复杂度是多少？
第二个题。。没有这么简单。说不定有的字母没有出现在单词的首字母中

in

【在 e****e 的大作中提到】

y*i2014-04-07 07:04

22 楼

don't know
closed them all before the annual fee hit

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

: 每张卡都有每年的10k miles吗？
:
: months

p*22014-04-07 07:04

23 楼

两两比较，直到只剩一个入度为0, 并且所有字母都包括了。

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

: 具体说说怎么根据字母顺序建图？难点在这里。

e*n2014-04-07 07:04

24 楼

新的那个4万点的卡看FT上怎么有人说是得交完年费后才给4万点呢？还有就是原来有3
万5的那张卡可以直接申请4万的吗，需要提前关卡么？多谢

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

: don't know
: closed them all before the annual fee hit

l*a2014-04-07 07:04

25 楼

能，WA的

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

: 你咋知道我是哪个厂的。。。。

y*i2014-04-07 07:04

26 楼

yes, previous offers were 35,000 miles, 1st year fee waived. current 40,000
miles offer doesn't waive the $89 AF.
in fact, $89 showed up in my account even before I got the card in the mail
I always closed the old ones before getting the new cards, others may have
done it differently

3

【在 e*********n 的大作中提到】

: 新的那个4万点的卡看FT上怎么有人说是得交完年费后才给4万点呢？还有就是原来有3
: 万5的那张卡可以直接申请4万的吗，需要提前关卡么？多谢

g*y2014-04-07 07:04

27 楼

two爷太牛了。当时就是开始的时候没有想到两两比较，结果卡在那里了。不过后半句
不对，因为你不知道字母的个数是多少。

【在 p*****2 的大作中提到】

:
: 两两比较，直到只剩一个入度为0, 并且所有字母都包括了。

e*n2014-04-07 07:04

28 楼

请问关卡后多久可以申请呢？需要等待多长时间才好

000
mail

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

: yes, previous offers were 35,000 miles, 1st year fee waived. current 40,000
: miles offer doesn't waive the $89 AF.
: in fact, $89 showed up in my account even before I got the card in the mail
: I always closed the old ones before getting the new cards, others may have
: done it differently
:
: 3

g*y2014-04-07 07:04

29 楼

好吧。。。。厂里不好混了，出来看看。你也是WA的？

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

: 能，WA的

y*i2014-04-07 07:04

30 楼

I usually wait one month, give or take a few days ...
personal preference, no science behind it
hehe

【在 e*********n 的大作中提到】

: 请问关卡后多久可以申请呢？需要等待多长时间才好
:
: 000
: mail

l*a2014-04-07 07:04

31 楼

不是，想去你们那里，好多牛人在那里
听说工资高，税少，房子便宜，还都是知名厂家

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

: 好吧。。。。厂里不好混了，出来看看。你也是WA的？

p*22014-04-07 07:04

32 楼

因为你不知道字母的个数是多少。
这个不可能吧？什么语言的字母数是动态的？

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

: two爷太牛了。当时就是开始的时候没有想到两两比较，结果卡在那里了。不过后半句
: 不对，因为你不知道字母的个数是多少。

e*e2014-04-07 07:04

33 楼

I guess it's n*lg(n) to build it. for each lookup, it's lg(n). The total
running time is n*lg(n)
http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22inter
Topo sort should be the way to go for Q2.

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

: 不太了解interval tree。说说复杂度是多少？
: 第二个题。。没有这么简单。说不定有的字母没有出现在单词的首字母中
:
: in

p*22014-04-07 07:04

34 楼

那先排序在查找也是nlogn

【在 e****e 的大作中提到】

: I guess it's n*lg(n) to build it. for each lookup, it's lg(n). The total
: running time is n*lg(n)
: http://www.dgp.utoronto.ca/people/JamesStewart/378notes/22inter
: Topo sort should be the way to go for Q2.

g*y2014-04-07 07:04

35 楼

工资高就算了。房子便宜倒是真的。

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

: 不是，想去你们那里，好多牛人在那里
: 听说工资高，税少，房子便宜，还都是知名厂家

g*y2014-04-07 07:04

36 楼

这个。。。。你假设你不知道是什么语言。

【在 p*****2 的大作中提到】

:
: 那先排序在查找也是nlogn

d*g2014-04-07 07:04

37 楼

不太了解interval tree。第一题这样做行么？
1，按start排序(O(nlogn))
2，遍历list，对list[i]来说，如果list[i].end > list[i+1].start,那么list[i].
conflict=true；或者如果list[0]到list[i-1]中end的最大值（endMax）是在list[i].
start到list[i].end之间的，那么list[i].conflict=true；然后更新endMax，++i。(O
(n))

g*y2014-04-07 07:04

38 楼

第一题有没有不需要用interval tree，比较老少咸宜的解法？

e*e2014-04-07 07:04

39 楼

You're right. Building the tree is 排序. Lookup the node is 查找. They are
essentially the same.

【在 p*****2 的大作中提到】

:
: 那先排序在查找也是nlogn

g*y2014-04-07 07:04

40 楼

不对。试试这个【1，9】，【2，3】，【4，5】

].
(O

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

: 不太了解interval tree。第一题这样做行么？
: 1，按start排序(O(nlogn))
: 2，遍历list，对list[i]来说，如果list[i].end > list[i+1].start,那么list[i].
: conflict=true；或者如果list[0]到list[i-1]中end的最大值（endMax）是在list[i].
: start到list[i].end之间的，那么list[i].conflict=true；然后更新endMax，++i。(O
: (n))

d*g2014-04-07 07:04

41 楼

把endMax 在list[i].start和list[i].end之间的判断改成 endMax > list[i].end 应
该就对了吧？

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

: 不对。试试这个【1，9】，【2，3】，【4，5】
:
: ].
: (O

g*y2014-04-07 07:04

42 楼

改成ENDMAX > list[i].begin?

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

:
: 把endMax 在list[i].start和list[i].end之间的判断改成 endMax > list[i].end 应
: 该就对了吧？

d*g2014-04-07 07:04

43 楼

嗯，你说的这个对~

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

: 改成ENDMAX > list[i].begin?

i*e2014-04-07 07:04

44 楼

第2题好像有问题，如果一本字典只有2个单词，比如：
ab
c
那我怎么知道c的顺序是在b之前还是之后。
原来我的想法是：
能不能从后往前读，并且每个单词也是从后往前读字母，如果第一次读到该字母
则输入，否则继续
好像也不对

l*a2014-04-07 07:04

45 楼

假定给你足够信息吧

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

: 第2题好像有问题，如果一本字典只有2个单词，比如：
: ab
: c
: 那我怎么知道c的顺序是在b之前还是之后。
: 原来我的想法是：
: 能不能从后往前读，并且每个单词也是从后往前读字母，如果第一次读到该字母
: 则输入，否则继续
: 好像也不对

p*22014-04-07 07:04

46 楼

sort就可以了。

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

: 第一题有没有不需要用interval tree，比较老少咸宜的解法？

r*n2014-04-07 07:04

47 楼

Q1:
I'm not familiar with interval tree. But I think you can solve it in the
following way:
put all start times in an array and sort it to get an array of indices with
increasing start times (the value of this array is the index, not the start
time)
similarly build an array of indices with increasing order of end times.
walk through the two arrays, if the values of the two arrays at the same
position are the same, that event is conflict free and mark it false. Mark
all other events true.
complexity O(nlogn)

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

r*n2014-04-07 07:04

48 楼

for Q2, I think an assumption has to be made, that is the alphabet is known.
otherwise, all words in the dictionary need be examined.

d*e2014-04-07 07:04

49 楼

Q2 Revised:
class Graph:
def __init__(self):
self.out_edges = {}
self.in_degrees = {}
def add_vertex(self, v):
if v not in self.out_edges:
self.out_edges[v] = []
self.in_degrees[v] = 0
def add_edge(self, v_out, v_in):
if v_in not in self.out_edges[v_out]:
self.out_edges[v_out].append(v_in)
self.in_degrees[v_in] += 1
def process_words(cur_word, next_word, graph):
for i in xrange(min(len(cur_word), len(next_word))):
if cur_word[i] != next_word[i]:
graph.add_vertex(cur_word[i])
graph.add_vertex(next_word[i])
graph.add_edge(cur_word[i], next_word[i])
break
def process_dictionary(dictionary):
graph = Graph()
for i in xrange(len(dictionary) - 1):
process_words(dictionary[i], dictionary[i+1], graph)
topological_sort(graph)
def topological_sort(graph):
head = [v for v in graph.out_edges if graph.in_degrees[v] == 0]
if len(head) == 1:
print head[0],
for v in graph.out_edges[head[0]]:
graph.in_degrees[v] -= 1
del graph.out_edges[head[0]]
topological_sort(graph)
if __name__ == '__main__':
dictionary = ['ab', 'ac', 'bc', 'bd']
process_dictionary(dictionary)

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

g*y2014-04-07 07:04

50 楼

你那个process_dictionary funciton里面，只需要考虑两个相邻的word就可以了。没
必要挨个考虑。例如：ab ac ad 只需要考虑ab ac和ac ad就好了，没必要考虑ab ad。

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

: Q2 Revised:
: class Graph:
: def __init__(self):
: self.out_edges = {}
: self.in_degrees = {}
: def add_vertex(self, v):
: if v not in self.out_edges:
: self.out_edges[v] = []
: self.in_degrees[v] = 0
: def add_edge(self, v_out, v_in):

g*y2014-04-07 07:04

51 楼

then check all words.

known.

【在 r*********n 的大作中提到】

: for Q2, I think an assumption has to be made, that is the alphabet is known.
: otherwise, all words in the dictionary need be examined.

g*y2014-04-07 07:04

52 楼

不对。对于一个event a，如果在其开始之前有k个events开始，在其结束之前有k个
events结束，并不代表这个event a没有conflict。下面一个反例：
[1,9] [6,7] [5,8]

with
start

【在 r*********n 的大作中提到】

: Q1:
: I'm not familiar with interval tree. But I think you can solve it in the
: following way:
: put all start times in an array and sort it to get an array of indices with
: increasing start times (the value of this array is the index, not the start
: time)
: similarly build an array of indices with increasing order of end times.
: walk through the two arrays, if the values of the two arrays at the same
: position are the same, that event is conflict free and mark it false. Mark
: all other events true.

p*22014-04-07 07:04

53 楼

我准备做做这题，你给几个test case好吗？

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

: 不对。对于一个event a，如果在其开始之前有k个events开始，在其结束之前有k个
: events结束，并不代表这个event a没有conflict。下面一个反例：
: [1,9] [6,7] [5,8]
:
: with
: start

p*22014-04-07 07:04

54 楼

那你只能全扫一遍了。不过这个复杂度太高了。

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

: 这个。。。。你假设你不知道是什么语言。

g*y2014-04-07 07:04

55 楼

我也都是现想的test case，没有现成的。

【在 p*****2 的大作中提到】

:
: 那你只能全扫一遍了。不过这个复杂度太高了。

g*y2014-04-07 07:04

56 楼

也不高， linear的。dictionary不一定包含所有的单词，我只是举了例子。你可以把
它看成list of string。

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

: 我也都是现想的test case，没有现成的。

p*22014-04-07 07:04

57 楼

看看这个对不
void setEvents(ArrayList al)
{
Collections.sort(al);
int max=Integer.MIN_VALUE;

for(int i=0;i{
Event e=al.get(i);
if(e.start<=max)
e.conflict=true;
max=Math.max(max, e.end);
}

int min=Integer.MAX_VALUE;

for(int i=al.size()-1;i>=0;i--)
{
Event e=al.get(i);
if(e.end>=min)
e.conflict=true;
min=Math.min(min, e.start);
}
}

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

: 我也都是现想的test case，没有现成的。

g*y2014-04-07 07:04

58 楼

第二个for loop是干什么的？感觉只用第一个for loop就可以了，不过要记录一下
event with the maximum end time, 然后每次后面有start time小于maximum end
time的event，就把两个都设成conflict。

【在 p*****2 的大作中提到】

:
: 看看这个对不
: void setEvents(ArrayList al)
: {
: Collections.sort(al);
: int max=Integer.MIN_VALUE;
:
: for(int i=0;i: {
: Event e=al.get(i);

c*m2014-04-07 07:04

59 楼

同球test case
写了一个，思想是这样的：
按照start 排序，取出当前的element（cur），然后往后check每个element（next）,
如果next的end是小于cur.end，说明next这个是被cur完全cover的；直到找到一个next
的end是大于cur.end，这样我们就可以更新cur了，直到遍历完。有点类似于蠕虫爬行
一样。
感觉虽然有两个loop，但是每个Event应该只比较了一次，遍历这块应该还是O(n)的吧
？当然sort的时候是O(nlgN).不知道这样对不对？一直在潜水，求指点，谢谢
int main()
{
Event e1(1, 9);
Event e2(2, 3);
Event e3(4, 5);
vector lVec;
lVec.push_back(e1);
lVec.push_back(e3);
lVec.push_back(e2);
std::sort(lVec.begin(), lVec.end());
int start = 0;
int end = 0;
std::vector::iterator pos = lVec.begin();
for(int i = 0;i < lVec.size(); )
{
start = lVec[i].start;
end = lVec[i].end;
int j = i + 1;
for(; j < lVec.size(); j++)
{
if (lVec[j].end < end)
{
lVec[j].conflict = true;
lVec[i].conflict = true;
}
else
break;
}
if ( j != lVec.size())
{
if (lVec[j].start < start)
{
lVec[j].conflict = true;
lVec[i].conflict = true;
}
}
// update i to next undetermined index
i = j;
}
}【在 gnahzy (hello) 的大作中提到: 】

p*22014-04-07 07:04

60 楼

后边的可能跟前边所有的都有overlap

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

: 第二个for loop是干什么的？感觉只用第一个for loop就可以了，不过要记录一下
: event with the maximum end time, 然后每次后面有start time小于maximum end
: time的event，就把两个都设成conflict。

t*r2014-04-07 07:04

61 楼

this one seems good :)

,
next

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

: 同球test case
: 写了一个，思想是这样的：
: 按照start 排序，取出当前的element（cur），然后往后check每个element（next）,
: 如果next的end是小于cur.end，说明next这个是被cur完全cover的；直到找到一个next
: 的end是大于cur.end，这样我们就可以更新cur了，直到遍历完。有点类似于蠕虫爬行
: 一样。
: 感觉虽然有两个loop，但是每个Event应该只比较了一次，遍历这块应该还是O(n)的吧
: ？当然sort的时候是O(nlgN).不知道这样对不对？一直在潜水，求指点，谢谢
: int main()
: {

a*l2014-04-07 07:04

62 楼

第二题很有意思。一般来说,一个字典每部分的第一词就是那个开始字母。如果是词不
全的字典，那么就没有底线了,极端的情况是只有一个词,无解。

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

g*r2014-04-07 07:04

63 楼

你这个思想是对的，但是感觉程序有问题，在跳出以后
if (lVec[j].start < start)
应该改成
if (lVec[j].start < end)
吧？

,
next

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

Y*f2014-04-07 07:04

64 楼

思路不错，练习了一下，去掉了双重循环
void eventConfl2(vector& events)
{
sort(events.begin(), events.end());
int end = events[0].end;
int frontIdx = 0;
for (int i = 1; i < events.size(); i++)
{
if (events[i].start < end)
{
events[frontIdx].conflict = true;
events[i].conflict = true;
if (events[i].end > end)
end = events[i].end;
}
else
{
frontIdx = i;
end = events[i].end;
}
}
}

,
next

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

e*s2014-04-07 07:04

65 楼

我也贴一个第一题，不知道对不对。
public static void setConflictEvent(ArrayList list){
Collections.sort(list);
Event temp = new Event(list.get(0).start, list.get(0).end, list.get(
0).conflict);

for(int i = 1; i < list.size(); i++)
{
if(temp.end > list.get(i).start)
{
list.get(i - 1).conflict = true;
list.get(i).conflict = true;

temp.end = Math.max(temp.end, list.get(i).end);
}
else
{
temp.start = list.get(i).start;
temp.end = list.get(i).end;
}
}
}

w*x2014-04-07 07:04

66 楼

第一题不需要build interval tree那么麻烦吧，把所有结点部分启始还是结束混在一
起排序，然后扫描一遍， n=0, 遇到开始端点 n++, 遇到结束端点 n--, 遇到开始端
点的时候如果n > 0设置那个开始端点对应的线段conflict flag为true

l*b2014-04-07 07:04

67 楼

得扫两遍吧，一次按开始端点升序排序，扫开始端点在不在之前的区间里，只要保持之
前的区间的结束端点的max就行
第二遍，按结束端点降序排序。扫结束端点在之前的区间里，保持之前区间的开始端点
的min就行。
又想了下，一遍够了。

【在 w****x 的大作中提到】

: 第一题不需要build interval tree那么麻烦吧，把所有结点部分启始还是结束混在一
: 起排序，然后扫描一遍， n=0, 遇到开始端点 n++, 遇到结束端点 n--, 遇到开始端
: 点的时候如果n > 0设置那个开始端点对应的线段conflict flag为true

c*t2014-04-07 07:04

68 楼

问题相当的严重
【1,3】【1,3】【1,3】

w*x2014-04-07 07:04

69 楼

struct EVENT
{
int nStart;
int nEnd;
bool bFlg;
EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
};
struct ENDPOINT
{
int nIndex;
bool bStart;
int nVal;
};
bool lessThan(const ENDPOINT& ed1, const ENDPOINT& ed2)
{
return ed1.nVal < ed2.nVal;
}
void setFlg(EVENT events[], int n)
{
if (events == NULL || n <= 0)
return;
ENDPOINT* ends = new ENDPOINT[n*2];
for (int i = 0; i < n; i++)
{
ends[2*i].bStart = true;
ends[2*i].nIndex = i;
ends[2*i].nVal = events[i].nStart;
ends[2*i+1].bStart = false;
ends[2*i+1].nIndex = i;
ends[2*i+1].nVal = events[i].nEnd;
}
std::sort(ends, ends+2*n, lessThan);
int nCount = 0;
for (int i = 0; i < 2*n; i++)
{
if (ends[i].bStart)
{
if (nCount > 0)
events[ends[i].nIndex].bFlg = true;
nCount++;
}
else
{
nCount--;
if (nCount > 0)
events[ends[i].nIndex].bFlg = true;
else if (!ends[i-1].bStart)
events[ends[i].nIndex].bFlg = true;
}
}
delete []ends;
}
void test()
{
EVENT events[] = {EVENT(1, 3), EVENT(2, 7), EVENT(4, 5), EVENT(6, 8),
EVENT(9, 10), EVENT(11, 12), EVENT(13, 16), EVENT(14, 15)};
setFlg(events, sizeof(events)/sizeof(EVENT));
}

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

: 得扫两遍吧，一次按开始端点升序排序，扫开始端点在不在之前的区间里，只要保持之
: 前的区间的结束端点的max就行
: 第二遍，按结束端点降序排序。扫结束端点在之前的区间里，保持之前区间的开始端点
: 的min就行。
: 又想了下，一遍够了。

w*x2014-04-07 07:04

70 楼

我加了一段end的判断逻辑，就是在end后平衡再check一下当前这段是否为全部cover
的情况，比如 [1, 15]全部cover[2,3] [5,7], 除了这种情况以一定会有一种不平衡
的状态出现

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

: 问题相当的严重
: 【1,3】【1,3】【1,3】

c*t2014-04-07 07:04

71 楼

好像可以，感觉只有你和二爷正确，我开始的想法和lucky一样，也是错的。

【在 w****x 的大作中提到】

:
: 我加了一段end的判断逻辑，就是在end后平衡再check一下当前这段是否为全部cover
: 的情况，比如 [1, 15]全部cover[2,3] [5,7], 除了这种情况以一定会有一种不平衡
: 的状态出现

l*h2014-04-07 07:04

72 楼

good idea.
一个Loop就够了。
我开始准备建立一个BST来查，虽然也是nlogn, 但是不如你这个简单。

,
next

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

l*b2014-04-07 07:04

73 楼

测了下，貌似没问题呀，感觉和merge interval哪个题一样
#include
#include
#include
using namespace std;
struct Interval {
int a;
int b;
bool cf;
Interval() : a(0), b(0), cf(false) {}
Interval(int start, int end) : a(start), b(end), cf(false) {}
};
bool compare(const Interval &s, const Interval &t) {
return s.a < t.a;
}
class Play {
public:
void setflag(vector &list) {
/* same idea as merge intervals, when intervals merge, they conflict
*/
sort(list.begin(), list.end(), compare);
int i = 0, n = list.size();
while(i < n) {
int m = list[i].b;
int j = i + 1;
while(j < n && list[j].a <= m) {
m = max(m, list[j].b);
list[j].cf = true;
++j;
}
if(j != i + 1) //化简了一下
list[i].cf = true;
i = j;
}
}
}
void printEvents(vector &list) {
int n = list.size();
for(int i = 0; i < n; ++i) {
cout << list[i].a << " " << list[i].b
<< (list[i].cf ? " Yes" : " ") << endl;
}
}
};
int main() {
Play pp;
vector l;
int s, t;
while(cin >> s) {
cin >> t;
Interval ev(s,t);
l.push_back(ev);
}
pp.setflag(l);
pp.printEvents(l);

return 0;
}

c*t2014-04-07 07:04

74 楼

test case [1,3][4,6][2,5] 能都设为conflict吗？

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

: 测了下，貌似没问题呀，感觉和merge interval哪个题一样
: #include
: #include
: #include
: using namespace std;
: struct Interval {
: int a;
: int b;
: bool cf;
: Interval() : a(0), b(0), cf(false) {}

w*x2014-04-07 07:04

75 楼

为啥要扫第二次？谁帮我看看下面这个解法对不对！
struct EVENT
{
int nStart;
int nEnd;
bool bFlg;
EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
};
bool lessThan(const EVENT& evt1, const EVENT& evt2)
{
return evt1.nStart < evt2.nStart;
}
void setFlg(EVENT events[], int n)
{
sort(events, events+n, lessThan);
int nMaxEndIndex = 0;
for (int i = 1; i < n; i++)
{
if (events[i].nStart <= events[nMaxEndIndex].nEnd)
{
events[i].bFlg = true;
events[nMaxEndIndex].bFlg = true;
}
if (events[i].nEnd >= events[nMaxEndIndex].nEnd)
nMaxEndIndex = i;
}
}

【在 p*****2 的大作中提到】

:
: 后边的可能跟前边所有的都有overlap

o*d2014-04-07 07:04

76 楼

惭愧的说,第二题我以前onsite见过,本行业的一个公司(不说名字了,估计很少有人去面
试),一个烙印,出了n多的算法题,其中一道就是这个.提示了半天,我也没有搞定,完全不
灵光....到现在我也不知道他希望我怎么做.

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

l*a2014-04-07 07:04

77 楼

除了你的ctor长的有点奇怪外，应该没什么问题

【在 w****x 的大作中提到】

:
: 为啥要扫第二次？谁帮我看看下面这个解法对不对！
: struct EVENT
: {
: int nStart;
: int nEnd;
: bool bFlg;
: EVENT(int a, int b) : nStart(a), nEnd(b) { bFlg = false; }
: };
: bool lessThan(const EVENT& evt1, const EVENT& evt2)

l*b2014-04-07 07:04

78 楼

测了下可以

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

: test case [1,3][4,6][2,5] 能都设为conflict吗？

c*t2014-04-07 07:04

79 楼

哦，那我错了，我开始想的是对的，被2爷带歪了。2爷第二个for loop看来是不需要的。

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

: 测了下可以

o*d2014-04-07 07:04

80 楼

???二爷的是 O(lg(n))+2n,你的是O(lg(n))+n^2阿,我看错了么?

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

: 测了下可以

l*b2014-04-07 07:04

81 楼

都是n log n + n，是两个循环，但是每个元素实际上只走一遍。

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

: ???二爷的是 O(lg(n))+2n,你的是O(lg(n))+n^2阿,我看错了么?

o*d2014-04-07 07:04

82 楼

???我看的不仔细?
你们的
loop(i=1...n)
loop(i+1...n)
这样每次一个i=1: n steps
i=2: n-1 steps
i=3: n-2 steps
totally: n+(n-1)+(n-2)....+1 = O(n^2)阿

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

: 都是n log n + n，是两个循环，但是每个元素实际上只走一遍。

l*b2014-04-07 07:04

83 楼

j < n && list[j].a <= m
j < n这个是虚的，保证不越界
后面 i = j，下个循环就从 j走起了不是 i + 1
1 ... n 分别由i 和 j 走一段一段，不走全程的

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

: ???我看的不仔细?
: 你们的
: loop(i=1...n)
: loop(i+1...n)
: 这样每次一个i=1: n steps
: i=2: n-1 steps
: i=3: n-2 steps
: totally: n+(n-1)+(n-2)....+1 = O(n^2)阿

o*d2014-04-07 07:04

84 楼

sorry,没有仔细看你们的程序,刚才仔细看了下,没错的.

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

: j < n && list[j].a <= m
: j < n这个是虚的，保证不越界
: 后面 i = j，下个循环就从 j走起了不是 i + 1
: 1 ... n 分别由i 和 j 走一段一段，不走全程的

l*b2014-04-07 07:04

85 楼

没，还是逻辑写得不够清晰。不容易写好呀

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

: sorry,没有仔细看你们的程序,刚才仔细看了下,没错的.