Sweep Line Algorithm - Implementation for 1D plane

Question

The problem is simple, There is some given 1D lines on a plane. We need to find the total size of space having at least one line.

Let me discuss this with an example image-

This may a case. Or

This may be a case or anything like this.

I know it is a basic problem of Sweep Line Algorithm.

But there is no proper document in the internet for it to understand properly.

The one best I have is a blog of Top Coder and that is here.

But it is not clear how to implement it or how may be the simulation.

If I want, we can do it in O(n^2) with 2 loops, but I can't realize how would be the procedure.

Or is there any better algorithm better than that O(n log n)?

Can anyone help me by sharing any Sudo Code or a simulation?

If Sudo code or example code is not available, a simulation for understanding is enough from where I can implement this.

---

Re- Problem calculating overlapping date ranges is not what I am looking because firstly, it is O(n^2) and so, it is not what I want. And it is not fully described like this question.

Answer 1

There is not so much info available for this topic.

So, I am sharing algorithm and a simulation with you which created by me for you and it is also with O(n log n) !!!!!

Let's start-

1. Create a priority list of all action points (action points are the starting or ending point of a line). And each item of the PQ has 3 elements (Current Point, Start or End, Comes from what line). (O(n log n) operation if we use Quick Short for sorting).
2. Initialize a Vector for storing current active lines.
3. Initialize an array of size = no of lines + 1 (for storing sum of shadow length).

4. Now remove a item from PQ and run specific operation for that item like described in the following images and you are done.

0

1

2

3

4

5

6

7

8

9

10

11

5. And do it until the PQ is empty.

In your case, find the sum of all the elements of the array from 1 to end (index no 1 to m) and it is your answer.

But with this algorithm and array, you can easily have many more complex question answers like what is the length of space having 3 shadow = Arr3 and so on.

Now the question is what's about order, right?

So, Sorting = O(n log n) and sweeping = O(m) [m=no of action points, so m

So, total order is = O(n log n) + O(m) = O(n log n)

Think you can understand it easily and will be a great help for you and many others. And think you will be able to easily implement it.