由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Insert bounding box
相关主题
BST的insertionMerge Interval 和 Insert Interval 需要用2分查找先定位到要merge的点么?
what's the difference of back_inserter and inserter in c++请教Merge Intervals 和 Insert Interval空间复杂度的选择。。。。
One interview question (A)收集了几个 List相关的题
leetcode 的 Insert Interval 就是过不了大的linkedin今天的电面题
这里还有比我更弱的么?问个我不太理解的问题--在别的地方看来的
google phone interview一道caeerCup上的难算法题
A的电面挂了,防不胜防啊Technical Aptitude Questions 中的一道题
Insert Interval large case测试没过,怎么优化?有疑问的一题
相关话题的讨论汇总
话题: bounding话题: boundbox话题: boxes话题: insert话题: box
进入JobHunting版参与讨论
1 (共1页)
l*********8
发帖数: 4642
1
A 2-D bounding box can represented as (Xmin, Xmax, Ymin, Ymax). We have a
set of bounding boxes. There is no intersection between any two of the
bounding boxes.

Now we want to insert one bounding box into the bounding boxes set and merge
the intersected bounding boxes if necessary. Two intersected boxes can be
merged into a big box like this:
Xmin = min(Xmin1, Xmin2); Xmax = max(Xmax1, Xmax2);
Ymin = min(Ymin1, Ymin2); Ymax = max(Ymax1, Ymax2);
Design an algorithm to do the insertion.
Example:
Exising bounding boxes set is { (1,4,0,2), (0,2,3,6) }
Bounding box to be inserted: (3,5,1,4)
Result: { (0, 5, 0, 6) }
b******u
发帖数: 81
2
递归。
public static List Insert(List boundBoxs, BoundBox boundBox)
{
List result = new List();
BoundBox bb = null;
int i;
for (i = 0; i < boundBoxs.Count(); i++)
{
bb = Merge(boundBoxs[i], boundBox);
if (bb != null)
{
break;
}
}
result.AddRange(boundBoxs);
if (bb == null)
{
result.Add(boundBox);
}
else
{
result.RemoveAt(i);
result = Insert(result, bb);
}
return result;
}
l*********8
发帖数: 4642
3
看了大概思路是对的。
这个算法复杂度是O(n^2)吧。 有没有更好的算法?

boundBox)

【在 b******u 的大作中提到】
: 递归。
: public static List Insert(List boundBoxs, BoundBox boundBox)
: {
: List result = new List();
: BoundBox bb = null;
: int i;
: for (i = 0; i < boundBoxs.Count(); i++)
: {
: bb = Merge(boundBoxs[i], boundBox);
: if (bb != null)

p*****2
发帖数: 21240
4

感觉很难比n^2好的。

【在 l*********8 的大作中提到】
: 看了大概思路是对的。
: 这个算法复杂度是O(n^2)吧。 有没有更好的算法?
:
: boundBox)

1 (共1页)
进入JobHunting版参与讨论
相关主题
有疑问的一题这里还有比我更弱的么?
问个经典问题的improvementgoogle phone interview
问个简单的GooG题目A的电面挂了,防不胜防啊
一个data structure design的问题,求助Insert Interval large case测试没过,怎么优化?
BST的insertionMerge Interval 和 Insert Interval 需要用2分查找先定位到要merge的点么?
what's the difference of back_inserter and inserter in c++请教Merge Intervals 和 Insert Interval空间复杂度的选择。。。。
One interview question (A)收集了几个 List相关的题
leetcode 的 Insert Interval 就是过不了大的linkedin今天的电面题
相关话题的讨论汇总
话题: bounding话题: boundbox话题: boxes话题: insert话题: box