Solution: Sweeping line is the right solution for this type of problem. Also the algorithm to this problem is the building block to solve the problem of total area covered by as set of overlapping rectangles. The following gives the detail of the algorithm:
- First, sort the points (start and end) of all the segments.
- Have a event queue and a counter cnt. cnt is used to store the number of active segments. When encountering a point p, first look at cnt, if cnt > 0, there must be a previous point p' ( p' is the point in the queue that is immediately before p) in the queue, add p'-p to the total length covered. Then add the current point p into the queue. If it is a start point, increase cnt by 1. If it is an end point, decrease cnt by 1.
- After iterating all the end points, we get the total length covered. We can also choose not to use cnt. Then we need to watch the size of the queue. Besides, when encountering an end point, we need also to remove some corresponding points in the queue, which is more complicated.
i didnt get your algo....
ReplyDeletesuppose input is ;
[1,3], [2,5], [6,7]
after sorting we get : 1,2,3,5,6,7
cnt=0;
1,2,3,5,6,7
adding 1 to the queue. cnt1=1
adding 2 to the queue. cnt=2
next element is 3.
now your algo says:
/*
When encountering an end point p, first look at cnt, if cnt > 0, there must be a previous end point p' in the queue, add p'-p to the total length covered.
*/
but queue has 1,2 only and both of them are starting point.
so there is no p` in the queue(i.e previous end point )...then what to do???
Sorry for the confusion. The part you mentioned should be "a point p", not "an end point p". Please see the updated post.
DeleteSuppose we have input as [1,3], [2,5], [6,7]. After sorting we get : 1,2,3,5,6,7 and cnt=0.
1) when encountering "1", since cnt=0, add "1" to the queue. Since "1" is a start point, increase cnt by 1.
2) when encountering "2", since cnt=1, add "2-1" to the total length. Also add "2" to the queue. Since "2" is a start point, increase cnt by 1.
3) when encountering "3", since cnt=2, add "3-2" to the total length. Also add "3" to the queue. Since "3" is an end point, decrease cnt by 1.
4) when encountering "5", since cnt=1, add "5-3" to the total length. Also add "5" to the queue. Since "5" is an end point, decrease cnt by 1.
5) when encountering "6", since cnt=0, only add "6" to the queue. Since "6" is a start point, increase cnt by 1.
6) when encountering "7", since cnt=1, add "7-6" to the total length. Also add "7" to the queue. Since "7" is an end point, decrease cnt by 1.