这可能是一个案例。或者
这可能是一个案例或类似的事情。
我知道这是扫描线算法的一个基本问题。
但是在互联网上没有适当的文献来正确理解它。
我拥有最好的一篇博客，来自Top Coder，在这里。
但是不清楚如何实现它或仿真模拟如何执行。
如果愿意，我们可以用两个循环在O(n^2)内完成，但我无法想象程序应该是什么样子。
还有比O(nlogn)更好的算法吗？
有人能通过分享任何Sudo代码或仿真来帮助我吗？
如果Sudo代码或示例代码不可用，则了解的仿真足以让我实现此功能。
重新-计算重复日期范围的问题不是我想要的，因为首先它的时间复杂度为O(n^2)，所以不符合我的要求。而且它没有像这个问题那样完全描述清楚。
这个主题的信息不是很多。
因此，我会向您分享由我创建的算法和模拟，它们是用 O(n log n) 实现的！
让我们开始吧-
0
1
2
3
4
5
6
7
数字 8
数字 9
数字 10
数字 11
在您的情况下，查找数组从 1 到 end（索引号为 1 到 m）中所有元素的和，这就是您的答案。
但是，使用此算法和数组，您可以轻松地获得更多复杂的问题答案，例如具有 3 个阴影的空间长度 = Arr3 等。
现在问题是关于顺序，对吧？
因此，排序 = O(n log n)， 扫描 = O(m) [m=动作点数，所以 m < n]。
因此，总顺序为 = O(n log n) + O(m) = O(n log n)
相信您能轻松理解它，这将对您和许多其他人有很大帮助。并且认为您可以轻松实现它。
这里有一种方法，你可以尝试一下（使用C＃编写。我没有测试过，所以请原谅可能存在的打字错误等问题;只需理解“思路”/策略）。
性能为O（N log m），其中m是您将创建的不相交的“阴影”数量。因此，在最坏情况下（如果所有线段都与其阴影不相交），您将具有O（N logN）的复杂度，但当只有几个阴影时，它基本上是O（N）。
public class LineSegment
{
public int Begin;
public int End;
// assumed to INCLUDE Begin but EXCLUDE End, so that
// length = End-Begin
public LineSegment Clone()
{
LineSegment clone = new LineSegment();
clone.Begin=this.Begin;
clone.End = this.End;
return clone;
}
}
public int TotalShadow(LineSegment[] segments)
{
// Class LineSegment has int members Begin and End, and Clone method to create a (shallow) Copy.
// Can/should be adapted if we're dealing with LineSegments with double/float coordinates.
// Easy special cases: no segements at all, or precisely one.
int N = segments.Length;
if (N == 0)
return 0;
else if (N == 1)
return (segments[0].End - segments[0].Begin);
// build a list of disjoint "shadows", cast onto the x-axis by all line segments together,
// sorted by their "Begin" (leftmost coordinate).
List<LineSegment> shadows = new List<LineSegment>();
// Initialize with the first segment, for convenient iteration below.
shadows.Add(segments[0].Clone());
for (int k = 1; k < N; ++k) // start at #1: we handled #0 already.
{
// find its position (Begin) in relation to the existing shadows (binary search).
int xBegin = segments[k].Begin;
int jLow = 0;
int xLow = shadows[jLow].Begin;
int jHigh, xHigh;
if (xBegin <= xLow)
jHigh = jLow; // avoid any more binary searching below
else
{
jHigh = shadows.Count - 1;
xHigh = shadows[jHigh].Begin;
if (xBegin >= xHigh)
jLow = jHigh; // avoid any more binary searching below
}
while (jHigh - jLow > 1)
{
int jTry = (jLow + jHigh) / 2;
int xTry = shadows[jTry].Begin;
if (xTry <= xBegin)
jLow = jTry;
else
jHigh = jTry;
}
// If it starts BEFORE "low" we create a new one: insert at jLow;
// Elseif x falls INSIDE "low", we merge it with low;
// ELSE we create a new shadow "between" low and high (as regards Begin)
// In all cases we'll make sure jLow points to the applicable shadow (new or existing).
// Next we'll check whether it overlaps with adjacent higher-lying shadows; if so: merge.
if (xBegin < shadows[jLow].Begin)
shadows.Insert(jLow, segments[k].Clone()); // jLow now points to the inserted item
else if (xBegin <= shadows[jLow].End)
{ // merge: extend existing low if applicable.
if (segments[k].End > shadows[jLow].End)
shadows[jLow].End = segments[k].End;
}
else // if (xBegin > shadows[jLow].End)
shadows.Insert(++jLow, segments[k].Clone()); // jLow increased to point to the inserted item.
// Try to merge, starting at the next higher lying shadow.
jHigh = jLow + 1;
while (jHigh < N && shadows[jLow].End >= shadows[jHigh].Begin)
jHigh++; // jHigh will point to the first one that we do NOT merge with.
if (jHigh > jLow + 1) // any merges?
{
if (shadows[jHigh - 1].End > shadows[jLow].End)
shadows[jLow].End = shadows[jHigh - 1].End; // set the appropriate End.
for (int jRemove = jHigh - 1; jRemove > jLow; --jRemove)
shadows.RemoveAt(jRemove); // Remove all shadaow-entries that we've merged with.
}
}
// Wrap up.
int shadowTotal = 0;
foreach (LineSegment shadow in shadows)
shadowTotal += (shadow.End - shadow.Begin);
return shadowTotal;
}
X和起始点的+1属性以及终止点的-1属性A。O（N）X键对数组进行排序。O（NlogN）CurrCount初始化为零，遍历数组，将A属性添加到CurrCount中。O（N）CurrCount大于零（已覆盖）和CurrCount等于零（未覆盖）的范围。这并不是很复杂。
创建一个数组，将所有区间端点的横坐标和标志放入其中，以表示其为起始点或结束点。
递增排序该数组。
然后扫描该数组并更新计数器：起始点会增加计数器，结束点会减少计数器。
所需大小可以轻松地从计数器从零变为非零或反之处的值中找到。
我认为无法比O(N Log(N))更快地完成此操作，因为需要进行排序（我认为无法避免），除非数据允许线性时间排序（例如直方图排序）。
也许您可以比盲目排序做得更好，采用以下方案，该方案源自MergeSort：
假设您有两个非重叠区间列表，按增加的边界排序；
执行类似于MergeSort的合并步骤（始终从每个列表移动到最接近的边界），以计算区间的并集；
根据两个列表的索引奇偶性，您可以确定要发出哪些边界（例如，使用ACBDEF排序AB和CDEF进行合并，则输出将为ADEF）。
这是一个线性时间操作。
利用这个修改后的合并，您可以实现一个修改后的MergeSort，它从单个区间开始递归形成联合。最终，您会得到一个单独的区间列表，该列表将为您提供所需的大小。
在最坏的情况下，没有边界会消失，过程仍然是O(N Log(N))。但是，当足够多的区间联合出现时，区间数量减少，处理时间可以降至线性O(N)。