扫线算法-一维平面的实现 [英] Sweep Line Algorithm - Implementation for 1D plane

问题描述

问题很简单，在平面上有一些给定的1D线。
我们需要找到至少有一行的空间总大小。

让我用示例图像进行讨论-

可能是这样。或

可能是这种情况

我知道这是

4. 现在从 PQ 中删除一个项目，并对该项目运行特定的操作，如下图所示，就完成了。

0

1

2

3

4

5

6

7

8

9

10

11

5. 然后执行直到PQ为空。

在您的情况下，请找出所有数组的元素从1到结尾（索引号1到m），这就是您的答案。

但是使用此算法和数组，您可以轻松地实现更复杂的处理问题答案，例如具有3个阴影的空间的长度是多少= Arr 3 依此类推。

现在是一个问题是关于订单的内容，对吗？

所以，排序= O（n log n）
而清扫= O（m） [m =没有动作要点，所以m

因此，总阶数= O（n log n）+ O（m）= O（n log n）

认为您可以轻松理解它，对您和其他许多人都会有很大的帮助。并且认为您将能够轻松实现它。

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.

解决方案

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.

这篇关于扫线算法-一维平面的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！