x********o
发帖数: 519 | 1 how to solve it? have no clue.
一维数轴上有 n 条线段，它们的端点都是已知的。请设计一个算法，计算出这些线
段的并集在数轴上所覆盖的长度，并分析时间复杂度。例如，线段 A 的坐标为[4, 8]
，线段 B 的坐标为[1, 5.1]， 那么它们共同覆盖的长度为 7。 请尽量找出最优化的
算法 |
R*******d
发帖数: 13640 | |
f*****w
发帖数: 2602 | 3 只能想出NlogN的 先按照线段左端的点排序 然后走一遍
不知道怎么样还能更好的没有 |
x********o
发帖数: 519 | 4 can you say more details about your approach.
I do not think it is NlogN.
【在 f*****w 的大作中提到】
: 只能想出NlogN的 先按照线段左端的点排序 然后走一遍
: 不知道怎么样还能更好的没有
|
o*****e
发帖数: 99 | 5 search "interval tree"
O(nlogn) to setup tree.
should be O(logn) to gather the total length.
so result should be o(nlogn) |
g*********e
发帖数: 14401 | 6 my solution.
sort the start & end O(nlogn)
then
O(n) time to get the length.
do a traversal,
use a variable (t) to store level of interleaving at the current position.
once encounter a start, t++,
once encounter an end, t--,
add the accumulated length at each step as long as t>0 |
