l*********y
发帖数: 142 | 1 一维数轴上有 n 条线段，它们的端点都是已知的。请设计一个算法，计算出这些线段
的并集在数轴上所覆盖的长度，并分析时间复杂度。例如，线段 A 的坐标为[4, 8]，
线段 B 的坐标为[1, 5.1]， 那么它们共同覆盖的长度为 7。 请尽量找出最优化的算
法， 解释算法即可，不必写代码。
帖子里没有答案。 |
s**9
发帖数: 207 | 2 这样对不对：
Let S be the set of the segments, and L(S) be the solution.
L(S){
find l, the longest segment one in S;
divide S into two sets S1 and S2, S1 contains all segments whose right
end is to the left of the right end of l, and S2 contains all segments whose
left end is to the right of the left end of l, i.e.,
S1 S2 |
l*****a
发帖数: 14598 | 3 keep a sorted linked list for the give pairs
for [ai,bi] [ai+1,bi+1]
if (ai>bi+1)||(ai+1>bi)
put both those 2 pairs into the right location of the linked list
(in order)
else
merge them into one pair and put into the right location of the linked
list(you can use binary search for this step)
the final result is the linked list.
I assume that u can get the result with O(nlogn) time complexity
【在 l*********y 的大作中提到】
: 一维数轴上有 n 条线段，它们的端点都是已知的。请设计一个算法，计算出这些线段
: 的并集在数轴上所覆盖的长度，并分析时间复杂度。例如，线段 A 的坐标为[4, 8]，
: 线段 B 的坐标为[1, 5.1]， 那么它们共同覆盖的长度为 7。 请尽量找出最优化的算
: 法， 解释算法即可，不必写代码。
: 帖子里没有答案。
|
l******o
发帖数: 144 | 4 随便写了一个，懒得去测试了。
#include
#include
#include
#include
#include
using namespace std;
template
struct Segment
{
T left;
T right;
};
template
struct LeftEndComp
{
bool operator () (const Segment& one, const Segment& two) const
{
return one.left < two.left || (!(two.left < one.left) && one.right <
two.right);
}
};
template
T coverage(const vector >& segments)
{
if(se
【在 l*********y 的大作中提到】
: 一维数轴上有 n 条线段，它们的端点都是已知的。请设计一个算法，计算出这些线段
: 的并集在数轴上所覆盖的长度，并分析时间复杂度。例如，线段 A 的坐标为[4, 8]，
: 线段 B 的坐标为[1, 5.1]， 那么它们共同覆盖的长度为 7。 请尽量找出最优化的算
: 法， 解释算法即可，不必写代码。
: 帖子里没有答案。
|
g*******y
发帖数: 1930 | 5 赞，拿到offer后还坚持做题目写code，不容易啊！
【在 l******o 的大作中提到】
: 随便写了一个，懒得去测试了。
: #include
: #include
: #include
: #include
: #include
: using namespace std;
: template
: struct Segment
: {
|
l******o
发帖数: 144 | 6 facebook后来发了offer letter，但是给的股票相当之少，所以有些犹豫要不要去
facebook了。现在在面别的公司。希望能有更满意的offer。
sigh~~~~
赞，拿到offer后还坚持做题目写code，不容易啊！
【在 g*******y 的大作中提到】
: 赞，拿到offer后还坚持做题目写code，不容易啊！
|
g*******y
发帖数: 1930 | 7 facebook股票的价值可能超过你想象吧。。。换我可能就满足了，呵呵
呵呵，看到个帖子里面说：
“
现在校园的童谣是这样说的,
顶尖学校的顶尖学生, 去脸书;
.....
.....
”
参考：
http://www.mitbbs.com/article_t/Seattle/31944641.html
【在 l******o 的大作中提到】
: facebook后来发了offer letter，但是给的股票相当之少，所以有些犹豫要不要去
: facebook了。现在在面别的公司。希望能有更满意的offer。
: sigh~~~~
:
: 赞，拿到offer后还坚持做题目写code，不容易啊！
|
c**********r
发帖数: 472 | 8 O(n)
List> data = //input from some where;
data.sort();
int inRangeCount=0;
int rangeStart = 0;
bool reset = true;
int overall = 0;
foreach(var v in data)
{
if(var.y==true)//start point
{
inRangeCount++;
}
else
{
inRangeCount--;
}
if(inRangeCount>0)
{
if(reset) rangeStart = v.x; reset = false;
}
else
{
overall += (v.x - rangeStart);
reset = true;
}
} |
S******a
发帖数: 862 | 9 唉~~被脸书无情鄙视的飘过~~
大神换了个头像都认不出来了。。。
话说谷歌
We would like to move forward with the hiring process for you.
以后是不是接近成功了？
有啥要注意的？
【在 g*******y 的大作中提到】
: facebook股票的价值可能超过你想象吧。。。换我可能就满足了，呵呵
: 呵呵，看到个帖子里面说：
: “
: 现在校园的童谣是这样说的,
: 顶尖学校的顶尖学生, 去脸书;
: .....
: .....
: ”
: 参考：
: http://www.mitbbs.com/article_t/Seattle/31944641.html
|
s******9
发帖数: 84 | 10 data.sort is not O(n).
【在 c**********r 的大作中提到】
: O(n)
: List> data = //input from some where;
: data.sort();
: int inRangeCount=0;
: int rangeStart = 0;
: bool reset = true;
: int overall = 0;
: foreach(var v in data)
: {
: if(var.y==true)//start point
|
l******o
发帖数: 144 | 11 con啊！
唉~~被脸书无情鄙视的飘过~~
大神换了个头像都认不出来了。。。
话说谷歌
We would like to move forward with the hiring process for you.
以后是不是接近成功了？
有啥要注意的？
【在 S******a 的大作中提到】
: 唉~~被脸书无情鄙视的飘过~~
: 大神换了个头像都认不出来了。。。
: 话说谷歌
: We would like to move forward with the hiring process for you.
: 以后是不是接近成功了？
: 有啥要注意的？
|
b********w
发帖数: 110 | 12 If we assume the following senario
1 3 4 8 |
