How do I improve this design for dealing with intersecting date ranges and resolving date range conflicts?

Question

I am working on some code that deals with date ranges. I have pricing activities that have a starting-date and an end-date to set a certain price for that range. There are multiple pricing activities with intersecting date ranges.

What I ultimately need is the ability to query valid prices for a date range. I pass in (jan1,jan31) and I get back a list that says jan1-->jan10 $4 , jan11-->jan19 $3 jan20-->jan31 $4.

There are priorities between pricing activities. Some type of pricing activities have high priority, so they override other pricing activities and for certain type of pricing activities lowest price wins etc.

I currently have a class that holds these pricing activities and keeps a resolved pricing calendar. As I add new pricing activities I update the resolved calendar. As I write more tests/code, it started to get very complicated with all the different cases (pricing activities intersecting in different ways). I am ending up with very complicated code where I am resolving a newly added pricing activity. See AddPricingActivity() method below.

Can anybody think of a simpler way to deal with this? Could there be similar code somewhere out there?

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

You could implement IComparable<T> and PricingActivity becomes sortable. I think, if I understand you correctly, that you would need to sort by range start, followed by priority. That way, when you query your sorted list, you get the first activity whose range would start and which has the highest priority. Then you just walk the list until you either: find an activity which starts after the last selected one ends, -or-, an activity with a higher priority than the last selected. When you have had the entire list, you should have selected the highest priority activities at each possible (sub)range interval.

Something like this: (not tested)

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 would contain an ordered list of activities which their applicable ranges (DateRange is just invented by me), just as you wanted. However, you'd have to add some code to first go to the first activity which is within the requested range, and stop at the first activity just outside the requested range.

Answer 2

A simple line sweep algorithm is what you're looking for. Essentially:

• Sort all of the starting and ending points of your pricing activities into an array of "events".
• Stepping through this array essentially gets you each pricing "event" as it happens (the beginning or ending of any pricing period).
• Scanning through this array in order lets you maintain a list of which acivities are in effect at any particular date.

So, given any date range, you can:

1. Start at the beginning of the array, with an empty "current activities set".
2. Look at each element in the array; if it's a start point, you add that activity to your current set; if it's an ending point, you drop that activity from the set.
3. Continue the sweep until you reach your desired date range.
4. As you're passing through your "output range", you can generate your valid price based on whatever activities are in the set; recalculating prices at every event step.
5. When you've scanned past the end of your desired range, you're done.

This way you don't need to maintain a potentially n! sized set of activity intersections, and you can generate your valid price list with a single O(n*a) pass (a being the average number of activities in the current set; close enough to linear if that's small / constant).

Answer 3

Some suggestions:-

1. Abstract DateTimeRange out of this. Do all the work of calculating overlaps, intersections and unions in a re-useable DateTimeRange class rather than here.

2. Don't try to update two data structures with insert, updates and deletes - both the source information and the resolved calendar - instead update the source data and then recalculate the resolved information using a simple sweep algorithm as others have suggested. If you NEED to cache the resolved calendar between changes to the source data, do that (clear cached copy whenever source changes and recalculate) otherwise just recalculate it every time because memory not CPU is typically the bottleneck these days and optimization is something you should do only if you need it.