单一维度内非重叠范围的数据结构 [英] Data structure for non-overlapping ranges within a single dimension

问题描述

我需要一个可以在一个维度内存储非重叠范围的数据结构。维度的整个范围不需要完全覆盖。

一个例子是会议室调度程序。维度是时间。没有两个时间表可能重叠。会议室并不总是安排。换句话说，在给定的时间内，最多可以有一个时间表。

一个快速的解决方案是用于存储开始和结束时间的范围。

 范围{
日期开始
日期结束
} 
  

这是非规范化的，要求容器不执行重叠。对于两个相邻的范围，上一个结束将在下一个开始时是多余的。

另一种方案可能涉及在每个范围内存储一个边界值。但是对于连续的范围序列，总是存在比范围多一个边界值。为了解决这个问题，序列可以表示为交替的边界值和范围：

B =边界值，r =范围

BrBrB

数据结构可能如下所示：

 边界{
日期值
范围prev 
范围next 
} 
 
范围{
边界开始
边界端
} 
  

本质上是一个具有交替类型的双向链表。

最终，我使用的任何数据结构都将在内存（应用程序代码）和关系数据库中进行表示。

我很好奇学术或行业尝试的解决方案存在。

解决方案

1. 对于不重叠的间隔，您可以按起点排序间隔。当您为此结构添加新的间隔时，您可以检查起始点和终点不属于此间隔集。要检查某点X是否属于间隔集，您可以使用二进制搜索来查找最近的起点，并检查X是否属于间隔。
   这种方法对于修改操作来说并不是最理想的。




2. 你可以看一下间隔树结构 - 对于非重叠间隔，它具有最佳查询和修改操作。

I need a data structure that can store non-overlapping ranges within a single dimension. The entire range of the dimension need not be completely covered.

An example would be a conference room scheduler. The dimension is time. No two schedules may overlap. The conference room isn't always scheduled. In other words, for a given time there can be at most one schedule.

A quick solution is for a range to store the start and end times.

Range {
    Date start
    Date end
}

This is non-normalized and requires the container to enforce no overlapping. For two adjacent ranges, the previous' end will be redundant with the next's start.

Another scheme might involve storing one boundary value with each range. But for a contiguous sequence of ranges, there will always be one more boundary values than ranges. To get around this the sequence could be represented as alternating boundary values and ranges:

B = boundary value, r = range

B-r-B-r-B

The data structure might look like:

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

In essence it's a doubly linked list with alternating types.

Ultimately, whatever data structure I use will be represented in both memory (application code) and a relational database.

I'm curious what academic or industry tried solutions exists.

解决方案

1. For non-overlapping intervals you could just sort you intervals with starting point. When you add a new interval to this structure, you could just check that start and end points do not belong to this interval set. To check whether some point X belong interval set you could use binary search to find the nearest start point and check that X belongs it's interval. This approach is not so optimal for modify operations.

2. You could look at Interval tree structure - for non-overlapping intervals it has optimal query and modify operations.

这篇关于单一维度内非重叠范围的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！