algorithm - 我想添加一些精细的速度范围并将它们保存到数据库中

Question

..这里我的问题是我应该检查速度范围是否重叠，如果它们重叠我应该显示一条消息说速度范围不能重叠。

Minimum  Maximum     Rate
1           15        10

16          25        15 

Answer 1

将每个速度范围视为连续数字线上的线段。为了找到所有的重叠，在每个线段重叠处划分数字线。

首先，将每个范围分为起点和终点。假设您的范围是:

(5,8) (1,5) (14,17) (3,4) (5,10)

为了清楚起见，我将给它们分配字母:

A=(5,8) B=(1,5) C=(14,17) D=(3,4) E=(5,10)

好的，现在，让我们将这些范围分成离散的起点和终点:

A[开始]=5，A[结束]=8，B[开始]=1，B[结束]=5，C[开始]=14，C[结束]=...等

按值对这些点进行排序，如果值相等，则起点在终点之前，这样您会得到如下列表:

B[开始]=1，D[开始]=3，D[结束]=4，A[开始]=5，E[开始]=5，B[结束]=5，A[ end]=8, ... 等

很简单，对吧？

现在，只需遍历您的排序列表，保留当前范围的列表。每次到达 [start] 点时，将该范围添加到列表中。每次到达 [end] 点时，从列表中取出范围。

所以对于上面的列表，你会去:

B[start]=1  add B =>    (B)
D[start]=3  add D =>    (B,D)
D[end]=3    remove D => (B)
A[start]=4  add A =>    (B,A)
E[start]=5  add E =>    (B,A,E)
B[end]=5    remove B => (A,E)
A[end]=8    remove A => (E)
  ... and so on

任何时候您的列表包含多个元素，这就是重叠。因此，对于任何范围，您都可以准确确定哪些范围在任何特定点重叠。

假设您使用像快速排序这样的算法对 being/end 点进行排序，这将是 O(n log n) 运行时间，并且检测实际重叠在时间上是线性的，所以整个算法将在 O(n log n) 内运行。