z**********g
发帖数: 209 | 1 有N个线段在一条直线上， 已知它们的起点和终点， 求覆盖的总长度。 线段可以有
overlap
Thanks. |
r********r
发帖数: 2912 | 2 sort by the starting point
then traverse from the first segment to the last one
【在 z**********g 的大作中提到】
: 有N个线段在一条直线上， 已知它们的起点和终点， 求覆盖的总长度。 线段可以有
: overlap
: Thanks.
|
g*********e
发帖数: 14401 | 3 perhaps can use divede and conquer
not sure exactly |
D*****d
发帖数: 1307 | 4 所有线段按起点排序
判断第一段和第二段是否重叠, 重叠就合并, 作为新的第一段, 继续
不重叠就单独拿出来, 以原来的第二段作为第一段, 继续
直到所有线段用完
觉得ARRAYLIST可能用起来比较方便 |
b***e
发帖数: 1419 | 5 不用。直接搞一个stack，起点就push，终点就pop，栈不空就加一段，栈空就skip。扫
一遍就可以。
说是栈，其实就是一个整数。判0即可。
【在 D*****d 的大作中提到】
: 所有线段按起点排序
: 判断第一段和第二段是否重叠, 重叠就合并, 作为新的第一段, 继续
: 不重叠就单独拿出来, 以原来的第二段作为第一段, 继续
: 直到所有线段用完
: 觉得ARRAYLIST可能用起来比较方便
|
r********r
发帖数: 2912 | 6 能说再详细一点吗，什么叫起点push终点pop啊...
【在 b***e 的大作中提到】
: 不用。直接搞一个stack，起点就push，终点就pop，栈不空就加一段，栈空就skip。扫
: 一遍就可以。
: 说是栈，其实就是一个整数。判0即可。
|
b***e
发帖数: 1419 | 7 // didn't test, but this is what it is:
// list is sorted.
covered = 0;
stack = 1;
for (i = 1; i < list.length; i++) {
if (stack > 0) {
covered += list[i] - list[i-1];
}
if (list[i] is a starting point) {
stack++;
} else { // if list[i] is an ending point
stack--;
}
} |
s*****y
发帖数: 897 | 8 Could this solution resolve the overlap scenario?
【在 b***e 的大作中提到】
: // didn't test, but this is what it is:
: // list is sorted.
: covered = 0;
: stack = 1;
: for (i = 1; i < list.length; i++) {
: if (stack > 0) {
: covered += list[i] - list[i-1];
: }
: if (list[i] is a starting point) {
: stack++;
|
b***e
发帖数: 1419 | 9 ya, I guess...
【在 s*****y 的大作中提到】
: Could this solution resolve the overlap scenario?
|
s*****y
发帖数: 897 | 10 your list[i] and list[i-1] is already sorted base on the input or not?
【在 b***e 的大作中提到】
: ya, I guess...
|
|
|
b*******8
发帖数: 37364 | 11 貌似可以简化一下，第一个左端点入Stack，记下坐标；当某个右端点来了造成Stack空
了，那么此右端点减去前面那个坐标，就是此条合起来大线段的长度。
covered = 0;
stack = 0;
for (i = 1; i < list.length; i++) {
//if (stack > 0) {
// covered += list[i] - list[i-1];
//}
if (list[i] is a starting point) {
if (stack == 0) left = list[i];
stack++;
} else { // if list[i] is an ending point
stack--;
if (stack == 0) covered += list[i] - left;
}
}
【在 b***e 的大作中提到】
: // didn't test, but this is what it is:
: // list is sorted.
: covered = 0;
: stack = 1;
: for (i = 1; i < list.length; i++) {
: if (stack > 0) {
: covered += list[i] - list[i-1];
: }
: if (list[i] is a starting point) {
: stack++;
|
h**********d
发帖数: 4313 | 12 不好意思，我大概没理解，如果都在一条直线上，为啥不能keep updating left 和
right， 这样traverse一遍不就有最左和最右了，然后相减得到长度
【在 z**********g 的大作中提到】
: 有N个线段在一条直线上， 已知它们的起点和终点， 求覆盖的总长度。 线段可以有
: overlap
: Thanks.
|
b*******8
发帖数: 37364 | 13 There are empty intervals. May not be covered totally.
【在 h**********d 的大作中提到】
: 不好意思，我大概没理解，如果都在一条直线上，为啥不能keep updating left 和
: right， 这样traverse一遍不就有最左和最右了，然后相减得到长度
|
h**********d
发帖数: 4313 | 14 got it
【在 b*******8 的大作中提到】
: There are empty intervals. May not be covered totally.
|
r********r
发帖数: 2912 | 15 I guess he already sorted the points
【在 s*****y 的大作中提到】
: your list[i] and list[i-1] is already sorted base on the input or not?
|
s*****y
发帖数: 897 | 16 Then it is not O(N) as sotrt take more than that already le.
【在 h**********d 的大作中提到】
: got it
|
