如何改进此设计以处理相交的日期范围并解决日期范围冲突？

Question

我正在编写一些处理日期范围的代码。我的定价活动有一个开始日期和一个结束日期，以便为该范围设置一定的价格。有多个具有交叉日期范围的定价活动。

我最终需要的是能够查询日期范围内的有效价格。我传入 (jan1,jan31) 并得到一个列表，其中显示 jan1-->jan10 $4 、 jan11-->jan19 $3 jan20-->jan31 $4 。

定价活动之间存在优先级。某些类型的定价活动具有高优先级，因此它们会覆盖其他定价活动，并且对于某些类型的定价活动，最低价格获胜等。

我目前有一个类来保存这些定价活动并保留已解决的定价日历。当我添加新的定价活动时，我会更新已解决的日历。 当我编写更多的测试/代码时，所有不同的情况（定价活动以不同的方式交叉）开始变得非常复杂。我最终得到了非常复杂的代码，我正在解决新添加的定价活动。请参阅下面的 AddPricingActivity() 方法。

有人能想出一个更简单的方法来处理这个问题吗？那里可能有类似的代码吗？

Public class PricingActivity()
{
    DateTime startDate;
    DateTime endDate;
    Double price;

    Public bool StartsBeforeEndsAfter (PricingActivity pAct)
    {
        // pAct covers this pricing activity
    }
    Public bool StartsMiddleEndsAfter (PricingActivity pAct){
        // early part of pAct Itersects with later part of this pricing activity 
    }
    //more similar methods to cover all the combinations of intersecting
}
Public Class PricingActivityList()
{
    List<PricingActivity> activities;
    SortedDictionary<Date, PricingActivity> resolvedPricingCalendar;
    Public void AddPricingActivity(PricingActivity pAct)
    {
        //update the resolvedCalendar
        //go over each activity and find intersecting ones 
        //update the resolved calendar correctly
        //depending on the type of the intersection
        //this part is getting out of hand…..
    }
}

Answer 1

您可以实现 IComparable 并且 PricingActivity 变得可排序。我认为，如果我理解正确的话，您需要按范围开始排序，然后按优先级排序。这样，当您查询排序列表时，您将获得范围将开始且具有最高优先级的第一个活动。然后，您只需遍历列表，直到找到以下任一活动：找到在最后选择的活动结束后开始的活动，或者-找到比最后选择的优先级更高的活动。当您拥有整个列表时，您应该在每个可能的（子）范围间隔中选择最高优先级的活动。

像这样的东西：（未经测试）

Date selectedStart = Date.MinValue;
PricingActivity selected = sortedList[0];
foreach(PricingActivity act in sortedList)
{
    if (act.Start >= selected.End ||
        act.Priority > selected.Priority)
    {
        // Store the selected activity with the applicable date range.
        selectedActivities.Add(
                new DateRange(selectedStart, Math.Min(selected.End, act.Start)),
                selected);
        // The next activity (act) would start here.
        selectedStart = act.Start;
        selected = act;
    }
}

selectedActivities 将包含其适用范围的活动的有序列表（DateRange 是我刚刚发明的），正如您想要的那样。但是，您必须添加一些代码才能首先转到请求范围内的第一个活动，并在请求范围之外的第一个活动处停止。

Answer 2

您正在寻找一个简单的线扫描算法。本质上：

• 将定价活动的所有起点和终点排序为一系列“事件”。
• 逐步浏览此数组本质上可以获取发生的每个定价“事件”（任何定价周期的开始或结束）。
• 按顺序扫描此数组可以让您维护在任何特定日期有效的活动的列表。

因此，对于给定的任何日期范围，您可以：

1. 从数组的开头开始，使用空的“当前活动集”。
2. 查看数组中的每个元素；如果它是一个起点，则将该活动添加到当前的集合中；如果它是终点，则从集合中删除该活动。
3. 继续扫描，直到达到所需的日期范围。
4. 当您通过“输出范围”时，您可以根据集合中的任何活动生成有效价格；在每个事件步骤重新计算价格。
5. 当您扫描超过所需范围的末尾时，您就完成了。

这样，您就不需要维护可能 n! 大小的活动交叉集，并且可以使用单个 O(n*a) 生成有效的价目表pass（a 是当前集合中活动的平均数量；如果它很小/恒定，则足够接近线性）。

Answer 3

一些建议：-

1. 从中抽象出 DateTimeRange 。在可重用的 DateTimeRange 类中完成计算重叠、交集和并集的所有工作，而不是在此处。

2. 不要尝试通过插入、更新和删除更新两个数据结构 - 源信息和解析的日历 - 而是更新源数据，然后使用简单的扫描重新计算解析的信息正如其他人所建议的算法。如果您需要在源数据更改之间缓存已解析的日历，请执行此操作（每当源更改时清除缓存的副本并重新计算），否则每次都重新计算它，因为内存而不是 CPU 通常是当今的瓶颈，优化是您应该做的事情仅当您需要时才这样做。