《突然发生的爱情故事》# Piebridge - 鹊桥
r*n
1 楼
就是给一堆interval，是在二维平面上的线段。把重合的线段都合并起来。
class Interval {
Point start;
Point end;
}
class Point {
int x; int y;
}
开始是想直接按照斜率和 start.x 排序就好了，结果发现不对，只能维持一个merge好
的序列，for循环往后，对于每个interval，找起点是不是在之前某个interval 组成的
线段上，这样时间复杂度是O(N^2),
各位大神有什么想法？
class Interval {
Point start;
Point end;
}
class Point {
int x; int y;
}
开始是想直接按照斜率和 start.x 排序就好了，结果发现不对，只能维持一个merge好
的序列，for循环往后，对于每个interval，找起点是不是在之前某个interval 组成的
线段上，这样时间复杂度是O(N^2),
各位大神有什么想法？
