由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 除了某家之外,讨论个F的面试题吧,merge 2D interval
相关主题
interview question:找包含点数最多的线段若问OJ的insert interval这题
关于面试中interval tree的问题请教Merge Intervals 和 Insert Interval空间复杂度的选择。。。。
Max points on a line问一个题目merge intervals
大家看看这几道google面试题怎么做?一道面试题。
讨论一道面试题问个merge interval的变体题
Merge Interval那道题这道linkedin题是不是应该用segment tree?
觉得G家很喜欢考interval的题,二爷要不总结一发?被烙印阴了: draw a line across two points
interval tree vs. merge intervalsInterview questions: points lie on same line
相关话题的讨论汇总
话题: interval话题: merge话题: point话题: 线段话题: 斜率
进入JobHunting版参与讨论
1 (共1页)
r*********n
发帖数: 32
1
就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。
class Interval {
Point start;
Point end;
}
class Point {
int x; int y;
}
开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好
的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的
线段上,这样时间复杂度是O(N^2),
各位大神有什么想法?
m**********s
发帖数: 518
2
目测用x^2+y^2排序,然后退化为按斜率的interval合并问题

【在 r*********n 的大作中提到】
: 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。
: class Interval {
: Point start;
: Point end;
: }
: class Point {
: int x; int y;
: }
: 开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好
: 的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的

l**********0
发帖数: 150
3
Groupby斜率进入map,每map内部的线段列表sortby x,y

【在 r*********n 的大作中提到】
: 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。
: class Interval {
: Point start;
: Point end;
: }
: class Point {
: int x; int y;
: }
: 开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好
: 的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的

F****n
发帖数: 3271
4
以斜率+截距为key建立hashtable
value为interval tree

【在 r*********n 的大作中提到】
: 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。
: class Interval {
: Point start;
: Point end;
: }
: class Point {
: int x; int y;
: }
: 开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好
: 的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的

s*****p
发帖数: 30
5
每个interval 所在的直线都和 x轴有一个交点 (x, 0)(和x轴平行的也要另外考虑)
能不能对于每个interval 计算出这个x的值和, 然后按x和斜率分组。
各个组内 在 interval[(x1, y1), (x2, y2)] 退化成[x1, x2], 然后按照x 排序 再
merge?
s******u
发帖数: 9
6
不知道这样行不行:可以自由平移的话就每个线段可以看作矢量(xend-xstart, yend-
ystart),然后搜索相等或相反的矢量就行了

【在 r*********n 的大作中提到】
: 就是给一堆interval,是在二维平面上的线段。把重合的线段都合并起来。
: class Interval {
: Point start;
: Point end;
: }
: class Point {
: int x; int y;
: }
: 开始是想直接按照斜率和 start.x 排序就好了,结果发现不对,只能维持一个merge好
: 的序列,for循环往后,对于每个interval,找起点是不是在之前某个interval 组成的

S*********r
发帖数: 42
7
1. First group by slope, log(N)
2. Within the same slope group, check colinearity by checking whether the
line of two starts has the same slope
3. Then we can merge the colinear lines
1 (共1页)
进入JobHunting版参与讨论
相关主题
Interview questions: points lie on same line讨论一道面试题
区间合并题的两种变体?Merge Interval那道题
Caeercup150 原题:Find a line passes most points觉得G家很喜欢考interval的题,二爷要不总结一发?
Leetcode 新题max points on a lineinterval tree vs. merge intervals
interview question:找包含点数最多的线段若问OJ的insert interval这题
关于面试中interval tree的问题请教Merge Intervals 和 Insert Interval空间复杂度的选择。。。。
Max points on a line问一个题目merge intervals
大家看看这几道google面试题怎么做?一道面试题。
相关话题的讨论汇总
话题: interval话题: merge话题: point话题: 线段话题: 斜率