p*****2
发帖数: 21240 | 1 我面试都用C，有些题觉得用C做比较麻烦。这就是一道。大家给评评。我现在也没有很
简洁的算法。
一个span array， 比如{(3,5),(7,16), (23,78)...}
然后给定一个span, 比如 （10，19）， 把这个span 跟 这个array merge.
当时没听明白，以为是两个array, 做到一半的时候才搞明白。
这题我上来就觉得C比较麻烦，所以我就说用C#吧，我想用List. 定义Node as
struct Node
{
int start;
int end;
}
后来编程的时候为了方便改成了class
class Node
{
int start;
int end;
Node(int s, int e)
{}
}
因为我主要是用C的，所以稍微有些措手不及。大家看看用C能有比较简洁的code吗？即
使用C#，我code写的也不好。大家帮我看看怎么改进。大概我写的是这样的
List Merge(List list, Node node)
{
List output;
int start=-1; //assume input are all positive numbers
int end=-1;
for(int i=0;i
{
if(start==-1)
{
if(list[i].endstart)
output.Add(list[i]);
else
{
start=min(list[i].start,node->start);
end=max(list[i].end,node->end);
}
}
else
{
if(list[i].start>end)
{
output.Add(new Node(start,end));
output.Add(list[i]);
start=-1;end=-1;
}
else
{
end=max(list[i].end,end);
output.Add(new Node(start,end));
start=-1;end=-1;
}
}
}
if(start!=-1) //this was a bug pointed out by interviewer
output.Add(new Node(start,end));
if(list[i-1].end
output.Add(node);
return output;
} |
S**N
发帖数: 182 | 2 不太明白
这个例子的输出应该是什么 谢谢
【在 p*****2 的大作中提到】
: 我面试都用C，有些题觉得用C做比较麻烦。这就是一道。大家给评评。我现在也没有很
: 简洁的算法。
: 一个span array， 比如{(3,5),(7,16), (23,78)...}
: 然后给定一个span, 比如 （10，19）， 把这个span 跟 这个array merge.
: 当时没听明白，以为是两个array, 做到一半的时候才搞明白。
: 这题我上来就觉得C比较麻烦，所以我就说用C#吧，我想用List. 定义Node as
: struct Node
: {
: int start;
: int end;
|
p*****2
发帖数: 21240 | 3
比如
{(3,5),(7,16), (23,78)}
（10，19）
输出
{(3,5),(7,19),(23,78)}
【在 S**N 的大作中提到】
: 不太明白
: 这个例子的输出应该是什么 谢谢
|
S**N
发帖数: 182 | 4 那如果是 {(3,5),(7,16), (23,78)}
(19,22)
输出应该是什么？
谢谢
【在 p*****2 的大作中提到】
:
: 比如
: {(3,5),(7,16), (23,78)}
: （10，19）
: 输出
: {(3,5),(7,19),(23,78)}
|
p*****2
发帖数: 21240 | 5
{(3,5),(7,16),(19,22),(23,78)}
【在 S**N 的大作中提到】
: 那如果是 {(3,5),(7,16), (23,78)}
: (19,22)
: 输出应该是什么？
: 谢谢
|
p*****2
发帖数: 21240 | 6
你这么一说我code里还有bug
【在 S**N 的大作中提到】
: 那如果是 {(3,5),(7,16), (23,78)}
: (19,22)
: 输出应该是什么？
: 谢谢
|
b*****c
发帖数: 1103 | 7 输出
(3,5),(7,16), (19,78)
咯 |
b*****c
发帖数: 1103 | |
p*****2
发帖数: 21240 | 9
靠。这题我问题太多了。
【在 b*****c 的大作中提到】
: 22,23是连续的咯，合并咯
|
p*****2
发帖数: 21240 | 10
你不说我一直没注意这点。
【在 b*****c 的大作中提到】
: 22,23是连续的咯，合并咯
|
|
|
w****x
发帖数: 2483 | 11 先对起点排序，排好了用下面的函数
void PrintMerge2(int a[], int n)
{
assert(a && n > 0 && n%2 == 0);
int nBeg = a[0];
int nEnd = a[1];
for (int i = 2; i < n; i += 2)
{
if (a[i] > nEnd)
{
cout<
nBeg = a[i];
nEnd = a[i+1];
}
else
{
if (a[i+1] > nEnd)
nEnd = a[i+1];
}
}
cout<
} |
p*****2
发帖数: 21240 | 12 这个interviewer在我写code的时候一直低头在laptop上貌似工作。我写一段想给他解
释一下，不见他抬头。最后只能一气写完，他抓了个bug就结束面试了。刚开始以为很
简单的题，后来越写code越乱。尤其是不得不转用C#写。 |
b*****c
发帖数: 1103 | 13 也没啥的，事后再重新写一下，很多interviewer都会抄下你的代码供committee看 |
p*****2
发帖数: 21240 | 14
你觉得这题用C好搞吗？最怕面C碰到Java程序员。上次面A也碰到这么一个。
【在 b*****c 的大作中提到】
: 也没啥的，事后再重新写一下，很多interviewer都会抄下你的代码供committee看
|
b*****c
发帖数: 1103 | 15 list (list span_lis, Node & span)
{
if (span_lis==NULL) return NULL;
list::iterator iter=span_lis.begin();
while (iter!=span_lis.end())
{
if ((*iter).second>=span.first-1)
{
(*iter).first=min((*iter).first,span.first);
(*iter).second=max((*iter).second,span.second);
while (++iter !=span_lis.end())
{
if ((*iter).first>*boost::prior(iter).second+1)
{
break;
}
else
if ((*iter).second>*boost::prior(iter).second)
{
*boost::prior(iter).second=(*iter).second;
span_lis.erase(iter--);
break;
}
else
{
span_lis.erase(iter--);
}
}
return span_lis;
}
iter++;
}
span_lis.push_back(span);
return span_lis;
} |
s******n
发帖数: 3946 | 16 不一定吧， 看成浮点就不用合并22,23
【在 p*****2 的大作中提到】
:
: 你觉得这题用C好搞吗？最怕面C碰到Java程序员。上次面A也碰到这么一个。
|
q****x
发帖数: 7404 | 17 algorithm: interval tree
coding: sort, binary search, sequential search.
【在 p*****2 的大作中提到】
: 我面试都用C，有些题觉得用C做比较麻烦。这就是一道。大家给评评。我现在也没有很
: 简洁的算法。
: 一个span array， 比如{(3,5),(7,16), (23,78)...}
: 然后给定一个span, 比如 （10，19）， 把这个span 跟 这个array merge.
: 当时没听明白，以为是两个array, 做到一半的时候才搞明白。
: 这题我上来就觉得C比较麻烦，所以我就说用C#吧，我想用List. 定义Node as
: struct Node
: {
: int start;
: int end;
|
z****u
发帖数: 104 | 18 这个应该就是一个 BST 的变种吧
按照 span 的 begin 值建立 BST
每次插入一个新的 span 的时候，如果这个span的 begin 值在某个 node 的范围之内
，合并，否则就是按照 BST 的规则进行插入
值得注意的是，合并的时候，需要判断合并后的 span 跟它的右儿子有没有相交，有的
话，继续合并，然后删除右儿子 |
p*****2
发帖数: 21240 | 19
删除右儿子用C操作起来还是有点麻烦。不过也还过得去。一会儿练练。这么看来这道
题出的也不算过分。用C的时候最后把后边的span往前移一下就可以了。
【在 z****u 的大作中提到】
: 这个应该就是一个 BST 的变种吧
: 按照 span 的 begin 值建立 BST
: 每次插入一个新的 span 的时候，如果这个span的 begin 值在某个 node 的范围之内
: ，合并，否则就是按照 BST 的规则进行插入
: 值得注意的是，合并的时候，需要判断合并后的 span 跟它的右儿子有没有相交，有的
: 话，继续合并，然后删除右儿子
|
p*****2
发帖数: 21240 | 20 再问个问题
recruiter跟我强调了多次，不要着急找出最优解，先找个solution work，写完代码然
后再improve。这算不是误导呀？ |
|
|
A**u
发帖数: 2458 | 21 没有误导你啊
这题目写起来也麻烦呢
【在 p*****2 的大作中提到】
: 再问个问题
: recruiter跟我强调了多次，不要着急找出最优解，先找个solution work，写完代码然
: 后再improve。这算不是误导呀？
|
n*******w
发帖数: 687 | 22 这个是正确的方向。一时找不出最优解，先brute force都行。你多点时间考虑或者实
现过程中能找到思路。
这个题应该不是语言的问题。用c或java基本也没差太多。
但是感觉你有些不清晰的地方。list用array还是linkedlist；合并的时候只要比较end
就行了，（start是先排好序的）这个逻辑要清晰。
interval的问题算是面试中比较繁琐的问题。
【在 p*****2 的大作中提到】
: 再问个问题
: recruiter跟我强调了多次，不要着急找出最优解，先找个solution work，写完代码然
: 后再improve。这算不是误导呀？
|
A**u
发帖数: 2458 | 23 你这也太夸张了
bst都用上了
得自己写一个bst?
面试来说，是不是太麻烦了
【在 z****u 的大作中提到】
: 这个应该就是一个 BST 的变种吧
: 按照 span 的 begin 值建立 BST
: 每次插入一个新的 span 的时候，如果这个span的 begin 值在某个 node 的范围之内
: ，合并，否则就是按照 BST 的规则进行插入
: 值得注意的是，合并的时候，需要判断合并后的 span 跟它的右儿子有没有相交，有的
: 话，继续合并，然后删除右儿子
|
n*******w
发帖数: 687 | 24 不麻烦的。用bst存interval，写递归。
跟树的遍历很类似。比预想简单的多。
只是直接用数组已经足够了。按start sort。
【在 A**u 的大作中提到】
: 你这也太夸张了
: bst都用上了
: 得自己写一个bst?
: 面试来说，是不是太麻烦了
|
s******n
发帖数: 3946 | |
s******n
发帖数: 3946 | |
y***d
发帖数: 2330 | 27 用 c 也不烦，想得太复杂了
newSpan=(10,19)
for each span in list
if overlap with newSpan
merge into newSpan
else
print span
print newSpan
这是没有 sort 的情况。
【在 p*****2 的大作中提到】
: 我面试都用C，有些题觉得用C做比较麻烦。这就是一道。大家给评评。我现在也没有很
: 简洁的算法。
: 一个span array， 比如{(3,5),(7,16), (23,78)...}
: 然后给定一个span, 比如 （10，19）， 把这个span 跟 这个array merge.
: 当时没听明白，以为是两个array, 做到一半的时候才搞明白。
: 这题我上来就觉得C比较麻烦，所以我就说用C#吧，我想用List. 定义Node as
: struct Node
: {
: int start;
: int end;
|
q****x
发帖数: 7404 | 28 如果不用区间树，那排序数组更简单。
【在 n*******w 的大作中提到】
: 不麻烦的。用bst存interval，写递归。
: 跟树的遍历很类似。比预想简单的多。
: 只是直接用数组已经足够了。按start sort。
|
a********m
发帖数: 15480 | 29 不算。过程比结果更重要。
【在 p*****2 的大作中提到】
: 再问个问题
: recruiter跟我强调了多次，不要着急找出最优解，先找个solution work，写完代码然
: 后再improve。这算不是误导呀？
|
p*****2
发帖数: 21240 | 30
可是他一直在搞电脑都不抬头看我呀。所以没啥过程了。
【在 a********m 的大作中提到】
: 不算。过程比结果更重要。
|
|
|
a********m
发帖数: 15480 | 31 "think loudly". 边写边说很重要。你写白伴的时候他们需要记录所有的代码，跟上你
的思路，也很忙的。
【在 p*****2 的大作中提到】
:
: 可是他一直在搞电脑都不抬头看我呀。所以没啥过程了。
|
g***x
发帖数: 494 | 32 这个好，但好像还少了点，merge 了 newspan之后，span i的end可能变化和i+1有重叠
，又要merge
【在 y***d 的大作中提到】
: 用 c 也不烦，想得太复杂了
: newSpan=(10,19)
: for each span in list
: if overlap with newSpan
: merge into newSpan
: else
: print span
: print newSpan
: 这是没有 sort 的情况。
|
p*****2
发帖数: 21240 | |
f*******t
发帖数: 7549 | 34 我以前写过一个程序，用linked list存interval，按起始位置排序，各线段不重叠。
要往里插入新的节点相当不好写对，有多种情况和边界条件。
interval tree概念是不复杂，面试中基本没可能写出来。 |
p*****2
发帖数: 21240 | 35 我面试都用C，有些题觉得用C做比较麻烦。这就是一道。大家给评评。我现在也没有很
简洁的算法。
一个span array， 比如{(3,5),(7,16), (23,78)...}
然后给定一个span, 比如 （10，19）， 把这个span 跟 这个array merge.
当时没听明白，以为是两个array, 做到一半的时候才搞明白。
这题我上来就觉得C比较麻烦，所以我就说用C#吧，我想用List. 定义Node as
struct Node
{
int start;
int end;
}
后来编程的时候为了方便改成了class
class Node
{
int start;
int end;
Node(int s, int e)
{}
}
因为我主要是用C的，所以稍微有些措手不及。大家看看用C能有比较简洁的code吗？即
使用C#，我code写的也不好。大家帮我看看怎么改进。大概我写的是这样的
List Merge(List list, Node node)
{
List output;
int start=-1; //assume input are all positive numbers
int end=-1;
for(int i=0;i
{
if(start==-1)
{
if(list[i].endstart)
output.Add(list[i]);
else
{
start=min(list[i].start,node->start);
end=max(list[i].end,node->end);
}
}
else
{
if(list[i].start>end)
{
output.Add(new Node(start,end));
output.Add(list[i]);
start=-1;end=-1;
}
else
{
end=max(list[i].end,end);
output.Add(new Node(start,end));
start=-1;end=-1;
}
}
}
if(start!=-1) //this was a bug pointed out by interviewer
output.Add(new Node(start,end));
if(list[i-1].end
output.Add(node);
return output;
} |
S**N
发帖数: 182 | 36 不太明白
这个例子的输出应该是什么 谢谢
【在 p*****2 的大作中提到】
: 我面试都用C，有些题觉得用C做比较麻烦。这就是一道。大家给评评。我现在也没有很
: 简洁的算法。
: 一个span array， 比如{(3,5),(7,16), (23,78)...}
: 然后给定一个span, 比如 （10，19）， 把这个span 跟 这个array merge.
: 当时没听明白，以为是两个array, 做到一半的时候才搞明白。
: 这题我上来就觉得C比较麻烦，所以我就说用C#吧，我想用List. 定义Node as
: struct Node
: {
: int start;
: int end;
|
p*****2
发帖数: 21240 | 37
比如
{(3,5),(7,16), (23,78)}
（10，19）
输出
{(3,5),(7,19),(23,78)}
【在 S**N 的大作中提到】
: 不太明白
: 这个例子的输出应该是什么 谢谢
|
S**N
发帖数: 182 | 38 那如果是 {(3,5),(7,16), (23,78)}
(19,22)
输出应该是什么？
谢谢
【在 p*****2 的大作中提到】
:
: 比如
: {(3,5),(7,16), (23,78)}
: （10，19）
: 输出
: {(3,5),(7,19),(23,78)}
|
p*****2
发帖数: 21240 | 39
{(3,5),(7,16),(19,22),(23,78)}
【在 S**N 的大作中提到】
: 那如果是 {(3,5),(7,16), (23,78)}
: (19,22)
: 输出应该是什么？
: 谢谢
|
p*****2
发帖数: 21240 | 40
你这么一说我code里还有bug
【在 S**N 的大作中提到】
: 那如果是 {(3,5),(7,16), (23,78)}
: (19,22)
: 输出应该是什么？
: 谢谢
|
|
|
b*****c
发帖数: 1103 | 41 输出
(3,5),(7,16), (19,78)
咯 |
b*****c
发帖数: 1103 | |
p*****2
发帖数: 21240 | 43
靠。这题我问题太多了。
【在 b*****c 的大作中提到】
: 22,23是连续的咯，合并咯
|
p*****2
发帖数: 21240 | 44
你不说我一直没注意这点。
【在 b*****c 的大作中提到】
: 22,23是连续的咯，合并咯
|
w****x
发帖数: 2483 | 45 先对起点排序，排好了用下面的函数
void PrintMerge2(int a[], int n)
{
assert(a && n > 0 && n%2 == 0);
int nBeg = a[0];
int nEnd = a[1];
for (int i = 2; i < n; i += 2)
{
if (a[i] > nEnd)
{
cout<
nBeg = a[i];
nEnd = a[i+1];
}
else
{
if (a[i+1] > nEnd)
nEnd = a[i+1];
}
}
cout<
} |
p*****2
发帖数: 21240 | 46 这个interviewer在我写code的时候一直低头在laptop上貌似工作。我写一段想给他解
释一下，不见他抬头。最后只能一气写完，他抓了个bug就结束面试了。刚开始以为很
简单的题，后来越写code越乱。尤其是不得不转用C#写。 |
b*****c
发帖数: 1103 | 47 也没啥的，事后再重新写一下，很多interviewer都会抄下你的代码供committee看 |
p*****2
发帖数: 21240 | 48
你觉得这题用C好搞吗？最怕面C碰到Java程序员。上次面A也碰到这么一个。
【在 b*****c 的大作中提到】
: 也没啥的，事后再重新写一下，很多interviewer都会抄下你的代码供committee看
|
b*****c
发帖数: 1103 | 49 list (list span_lis, Node & span)
{
if (span_lis==NULL) return NULL;
list::iterator iter=span_lis.begin();
while (iter!=span_lis.end())
{
if ((*iter).second>=span.first-1)
{
(*iter).first=min((*iter).first,span.first);
(*iter).second=max((*iter).second,span.second);
while (++iter !=span_lis.end())
{
if ((*iter).first>*boost::prior(iter).second+1)
{
break;
}
else
if ((*iter).second>*boost::prior(iter).second)
{
*boost::prior(iter).second=(*iter).second;
span_lis.erase(iter--);
break;
}
else
{
span_lis.erase(iter--);
}
}
return span_lis;
}
iter++;
}
span_lis.push_back(span);
return span_lis;
} |
s******n
发帖数: 3946 | 50 不一定吧， 看成浮点就不用合并22,23
【在 p*****2 的大作中提到】
:
: 你觉得这题用C好搞吗？最怕面C碰到Java程序员。上次面A也碰到这么一个。
|
|
|
q****x
发帖数: 7404 | 51 algorithm: interval tree
coding: sort, binary search, sequential search.
【在 p*****2 的大作中提到】
: 我面试都用C，有些题觉得用C做比较麻烦。这就是一道。大家给评评。我现在也没有很
: 简洁的算法。
: 一个span array， 比如{(3,5),(7,16), (23,78)...}
: 然后给定一个span, 比如 （10，19）， 把这个span 跟 这个array merge.
: 当时没听明白，以为是两个array, 做到一半的时候才搞明白。
: 这题我上来就觉得C比较麻烦，所以我就说用C#吧，我想用List. 定义Node as
: struct Node
: {
: int start;
: int end;
|
p*****2
发帖数: 21240 | 52
删除右儿子用C操作起来还是有点麻烦。不过也还过得去。一会儿练练。这么看来这道
题出的也不算过分。用C的时候最后把后边的span往前移一下就可以了。
【在 z****u 的大作中提到】
: 这个应该就是一个 BST 的变种吧
: 按照 span 的 begin 值建立 BST
: 每次插入一个新的 span 的时候，如果这个span的 begin 值在某个 node 的范围之内
: ，合并，否则就是按照 BST 的规则进行插入
: 值得注意的是，合并的时候，需要判断合并后的 span 跟它的右儿子有没有相交，有的
: 话，继续合并，然后删除右儿子
|
p*****2
发帖数: 21240 | 53 再问个问题
recruiter跟我强调了多次，不要着急找出最优解，先找个solution work，写完代码然
后再improve。这算不是误导呀？ |
A**u
发帖数: 2458 | 54 没有误导你啊
这题目写起来也麻烦呢
【在 p*****2 的大作中提到】
: 再问个问题
: recruiter跟我强调了多次，不要着急找出最优解，先找个solution work，写完代码然
: 后再improve。这算不是误导呀？
|
n*******w
发帖数: 687 | 55 这个是正确的方向。一时找不出最优解，先brute force都行。你多点时间考虑或者实
现过程中能找到思路。
这个题应该不是语言的问题。用c或java基本也没差太多。
但是感觉你有些不清晰的地方。list用array还是linkedlist；合并的时候只要比较end
就行了，（start是先排好序的）这个逻辑要清晰。
interval的问题算是面试中比较繁琐的问题。
【在 p*****2 的大作中提到】
: 再问个问题
: recruiter跟我强调了多次，不要着急找出最优解，先找个solution work，写完代码然
: 后再improve。这算不是误导呀？
|
A**u
发帖数: 2458 | 56 你这也太夸张了
bst都用上了
得自己写一个bst?
面试来说，是不是太麻烦了
【在 z****u 的大作中提到】
: 这个应该就是一个 BST 的变种吧
: 按照 span 的 begin 值建立 BST
: 每次插入一个新的 span 的时候，如果这个span的 begin 值在某个 node 的范围之内
: ，合并，否则就是按照 BST 的规则进行插入
: 值得注意的是，合并的时候，需要判断合并后的 span 跟它的右儿子有没有相交，有的
: 话，继续合并，然后删除右儿子
|
n*******w
发帖数: 687 | 57 不麻烦的。用bst存interval，写递归。
跟树的遍历很类似。比预想简单的多。
只是直接用数组已经足够了。按start sort。
【在 A**u 的大作中提到】
: 你这也太夸张了
: bst都用上了
: 得自己写一个bst?
: 面试来说，是不是太麻烦了
|
s******n
发帖数: 3946 | |
s******n
发帖数: 3946 | |
y***d
发帖数: 2330 | 60 用 c 也不烦，想得太复杂了
newSpan=(10,19)
for each span in list
if overlap with newSpan
merge into newSpan
else
print span
print newSpan
这是没有 sort 的情况。
【在 p*****2 的大作中提到】
: 我面试都用C，有些题觉得用C做比较麻烦。这就是一道。大家给评评。我现在也没有很
: 简洁的算法。
: 一个span array， 比如{(3,5),(7,16), (23,78)...}
: 然后给定一个span, 比如 （10，19）， 把这个span 跟 这个array merge.
: 当时没听明白，以为是两个array, 做到一半的时候才搞明白。
: 这题我上来就觉得C比较麻烦，所以我就说用C#吧，我想用List. 定义Node as
: struct Node
: {
: int start;
: int end;
|
|
|
q****x
发帖数: 7404 | 61 如果不用区间树，那排序数组更简单。
【在 n*******w 的大作中提到】
: 不麻烦的。用bst存interval，写递归。
: 跟树的遍历很类似。比预想简单的多。
: 只是直接用数组已经足够了。按start sort。
|
a********m
发帖数: 15480 | 62 不算。过程比结果更重要。
【在 p*****2 的大作中提到】
: 再问个问题
: recruiter跟我强调了多次，不要着急找出最优解，先找个solution work，写完代码然
: 后再improve。这算不是误导呀？
|
p*****2
发帖数: 21240 | 63
可是他一直在搞电脑都不抬头看我呀。所以没啥过程了。
【在 a********m 的大作中提到】
: 不算。过程比结果更重要。
|
a********m
发帖数: 15480 | 64 "think loudly". 边写边说很重要。你写白伴的时候他们需要记录所有的代码，跟上你
的思路，也很忙的。
【在 p*****2 的大作中提到】
:
: 可是他一直在搞电脑都不抬头看我呀。所以没啥过程了。
|
g***x
发帖数: 494 | 65 这个好，但好像还少了点，merge 了 newspan之后，span i的end可能变化和i+1有重叠
，又要merge
【在 y***d 的大作中提到】
: 用 c 也不烦，想得太复杂了
: newSpan=(10,19)
: for each span in list
: if overlap with newSpan
: merge into newSpan
: else
: print span
: print newSpan
: 这是没有 sort 的情况。
|
p*****2
发帖数: 21240 | |
f*******t
发帖数: 7549 | 67 我以前写过一个程序，用linked list存interval，按起始位置排序，各线段不重叠。
要往里插入新的节点相当不好写对，有多种情况和边界条件。
interval tree概念是不复杂，面试中基本没可能写出来。 |
w***y
发帖数: 6251 | 68 这题看起来简单, 做起来发现自己出很多错啊 555555
目前我比较了自己的答案和大家的讨论, 采用了这个方法. 本来我还用了一个新的list
记录, 还要看原list哪些被merge之后会引起后面的继续被merge//囧
【在 w****x 的大作中提到】
: 先对起点排序，排好了用下面的函数
: void PrintMerge2(int a[], int n)
: {
: assert(a && n > 0 && n%2 == 0);
: int nBeg = a[0];
: int nEnd = a[1];
: for (int i = 2; i < n; i += 2)
: {
: if (a[i] > nEnd)
: {
|
l*********y
发帖数: 142 | 69 #include
#include
#include
using namespace std;
struct Segment {
Segment(int l, int r) : left(l), right(r) {};
int left;
int right;
};
vector input;
vector output;
void MergeInput(vector& input, Segment& cand)
{
int left = cand.left;
int right = cand.right;
// 处理边界情况
if (input.size() == 0 || cand.right < input.front().left || cand.left >
input.back().right) {
output.push_back(Segment(cand.left, cand.right));
return;
}
bool insert = false;
for (int i = 0; i < input.size(); i++) {
Segment cur = input[i];
if (cand.right >= cur.left) {
if (cur.right >= cand.left) {
left = min(cur.left, left);
right = max(cur.right, right);
} else {
output.push_back(cur);
}
} else {
insert = true;
output.push_back(Segment(left, right));
output.push_back(cur);
}
}
// 注意结尾的处理
if (! insert) {
output.push_back(Segment(left, right));
}
}
int main() {
int left, right;
cin >> left >> right;
Segment cand(left, right);
while (cin >> left >> right) {
Segment cur(left, right);
input.push_back(cur);
}
MergeInput(input, cand);
for (int i = 0; i < output.size(); i++) {
cout << output[i].left << " " << output[i].right << endl;
}
return 0;
}
input:
10 19
3 5
7 10
19 21
23 78
output:
3 5
7 21
23 78
请大家看看。 |
g**********y
发帖数: 14569 | 70 我觉得这个差不多就是G expect to see的答案，left/right没必要，直接改cand就可以。
【在 l*********y 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: struct Segment {
: Segment(int l, int r) : left(l), right(r) {};
: int left;
: int right;
: };
: vector input;
|
|
|
g**********y
发帖数: 14569 | 71 写了个Java版的。这个题在interview时很不好写，尽是细节，到处都可以犯错误。容
易误入歧途的，是试图在输入list上直接改，那个写起来，就不是interview时间可以
写清楚的了。除非你是大牛，思路极其清楚。我是一定写一堆bug出来。
这里只是打印出来，生成新List是一样的。
private void merge(List list, Node newNode) {
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
Node node = iterator.next();
if (newNode.end < node.start) {
newNode.print();
node.print();
while (iterator.hasNext()) iterator.next().print();
return;
}
if (newNode.start > node.end) {
node.print();
}
else {
newNode.start = Math.min(newNode.start, node.start);
newNode.end = Math.max(newNode.end, node.end);
}
}
newNode.print();
}
private class Node {
int start;
int end;
public Node(int start, int end) {
this.start = start;
this.end = end;
}
public void print() {
System.out.println(this.start + ", " + this.end);
}
} |
d******u
发帖数: 397 | |
z****h
发帖数: 164 | 73 好像还是没处理相邻ｉｎｔｅｒｖｅｌ的合并。比如：（１７，２２），（２３， ７
８）应该变成（１７，７８）
【在 g**********y 的大作中提到】
: 写了个Java版的。这个题在interview时很不好写，尽是细节，到处都可以犯错误。容
: 易误入歧途的，是试图在输入list上直接改，那个写起来，就不是interview时间可以
: 写清楚的了。除非你是大牛，思路极其清楚。我是一定写一堆bug出来。
: 这里只是打印出来，生成新List是一样的。
: private void merge(List list, Node newNode) {
: Iterator iterator = list.iterator();
: while (iterator.hasNext()) {
: Node node = iterator.next();
:
: if (newNode.end < node.start) {
|
z****h
发帖数: 164 | 74 public class Pair{
int left;
int right;
Pair next;
public Pair(int left, int right)
{
this.left = left;
this.right = right;
this.next = null;
}
}
private Pair getPurgedPairs(Pair head)
{
if(head == null || head.next == null) return head;
Pair curr = head;
while(curr != null)
{
Pair next = curr.next;
while(next != null && next.left <= curr.right +1){
if(next.right > curr.right){
curr.right = next.right;
curr.next = next.next;
}else
{
curr.next = next.next;
}
next = curr.next;
}
if(next == null) break;
curr = next;
}
return head;
} |
