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.

asked Dec 24 '22 15:12
#### Abrar Jahin

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-

- 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). - Initialize a Vector for storing current active lines.
- Initialize an array of size = no of lines + 1 (for storing sum of shadow length).

- 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

- 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.

answered Jan 31 '23 10:01
#### Abrar Jahin

### Recent Activity

- Apple Pay - authorize.net returns error 153 only when live, sandbox works
- How to continue cursor loop even error occured in the loop
- python find all neighbours of a given node in a list of lists
- Fatal error: Call to a member function setColumn() on a non-object in Magento
- Count how many of each value from a field with MySQL and PHP
- Python 32-bit development on 64-bit Windows [closed]

If you love us? You can donate to us via Paypal or buy me a coffee
so we can maintain and grow! **Thank you!**