Finding lowest price for overlapping date ranges - C# algorithm

Question

There are prices set for certain time periods... I'm having trouble coming up with an algorithm to determine the lowest price for a specific time period.

I'm doing this with a list of objects, where the object has properties DateTime StartDate, DateTime EndDate, decimal Price.

For example, two price sets and their active date ranges:

A. 09/26/16 - 12/31/17 at $20.00
B. 12/01/16 - 12/31/16 at $18.00

You can see that B is inside the A time period and is lower.

I need that converted to this:

A. 09/26/16 - 11/30/16 at $20.00
B. 12/01/16 - 12/31/16 at $18.00
C. 01/01/17 - 12/31/17 at $20.00

It has to work for any number of date ranges and combinations. Has anyone come across anything I can manipulate to get the result I need? Or any suggestions?

Edit: My data structure:

public class PromoResult
{
    public int ItemId { get; set; }
    public decimal PromoPrice { get; set; }
    public DateTime StartDate { get; set; }
    public DateTime EndDate { get; set; }
    public int PromoType { get; set; } // can ignore this...
}

Answer 1

This is a great case for using Linq. Assuming your price range object is called PriceRecord...

You will need to create a list of all dates and then filter down to price records that are between two consecutive dates. An implementation might look something like this:

    public static IEnumerable<PriceRecord> ReduceOverlaps(IEnumerable<PriceRecord> source)
    {
        // Get a list of all edges of date ranges
        // edit, added OrderBy (!)
        var edges = source.SelectMany(record => new[] { record.StartDate, record.EndDate }).OrderBy(d => d).ToArray();
        // iterate over pairs of edges (i and i-1)
        for (int i = 1; i < edges.Length; i++)
        {
            // select min price for range i-1, i
            var price = source.Where(r => r.StartDate <= edges[i - 1] && r.EndDate >= edges[i]).Select(r => r.Price).Min();
            // return a new record from i-1, i with price
            yield return new PriceRecord() { StartDate = edges[i - 1], EndDate = edges[i], Price = price };
        }
    }

I haven't tested this and you may need to tinker with the comparison operators, but it may be a good starting point. I have now tested the code, the example here works with the data in the question.

Feel free to propose edits to improve this example.

Answer 2

Doesn't directly answer your question, but here is some SQL that I used to solve a similar problem I had (simplified down a bit, as I was also dealing with multiple locations and different price types):

SELECT RI.ItemNmbr, RI.UnitPrice, RI.CasePrice
    , RP.ProgramID
    , Row_Number() OVER (PARTITION BY RI.ItemNmbr,
                         ORDER BY CASE WHEN RI.UnitPrice > 0 
                                       THEN RI.UnitPrice
                                       ELSE 1000000 END ASC
                                  , CASE WHEN RI.CasePrice > 0
                                         THEN RI.CasePrice
                                         ELSE 1000000 END ASC
                                  , RP.EndDate DESC
                                  , RP.BeginDate ASC
                                  , RP.ProgramID ASC) AS RowNumBtl
    , Row_Number() OVER (PARTITION BY RI.UnitPrice, 
                         ORDER BY CASE WHEN RI.CasePrice > 0 
                                       THEN RI.CasePrice
                                       ELSE 1000000 END ASC
                                  , CASE WHEN RI.UnitPrice > 0
                                         THEN RI.UnitPrice
                                         ELSE 1000000 END ASC
                                  , RP.EndDate DESC
                                  , RP.BeginDate ASC
                                  , RP.ProgramID ASC) AS RowNumCase
  FROM RetailPriceProgramItem AS RI
    INNER JOIN RetailPriceMaster AS RP
        ON RP.ProgramType = RI.ProgramType AND RP.ProgramID = RI.ProgramID
  WHERE RP.ProgramType='S'
        AND RP.BeginDate <= @date AND RP.EndDate >= @date
                    AND RI.Active=1

I select from that where RowNumBtl=1 for the UnitPrice and RowNumCase=1 for the CasePrice. If you then create a table of dates (which you can do using a CTE), you can cross apply on each date. This is a bit inefficient, since you only need to test at border conditions between date ranges, so... good luck with that.

Answer 3

I will use 2 functions DateRange and GroupSequenceWhile

List<PromoResult> promoResult = new List<PromoResult>()
{
    new PromoResult() {  PromoPrice=20, StartDate = new DateTime(2016, 9, 26),EndDate=new DateTime(2017, 12, 31)},
    new PromoResult() {  PromoPrice=18, StartDate = new DateTime(2016, 12, 1),EndDate=new DateTime(2016, 12, 31)}
};

var result = promoResult.SelectMany(x => DateRange(x.StartDate, x.EndDate, TimeSpan.FromDays(1))
                                         .Select(y => new { promo = x, date = y }))
            .GroupBy(x => x.date).Select(x => x.OrderBy(y => y.promo.PromoPrice).First())
            .OrderBy(x=>x.date)
            .ToList();

var final = result.GroupSequenceWhile((x, y) => x.promo.PromoPrice == y.promo.PromoPrice)
            .Select(g => new { start = g.First().date, end = g.Last().date, price = g.First().promo.PromoPrice })
            .ToList();

foreach (var r in final)
{
    Console.WriteLine(r.price + "$ " + r.start.ToString("MM/dd/yy", CultureInfo.InvariantCulture) + " " + r.end.ToString("MM/dd/yy", CultureInfo.InvariantCulture));
}

---

OUTPUT:

20$ 09/26/16 11/30/16
18$ 12/01/16 12/31/16
20$ 01/01/17 12/31/17

---

Algorithm:

1- create a <day,price> tuple for each item in promoResult list

2- group this tuples by day and select min price

3- order this tuples by date

4- select the starting and ending day when there is a change in price in consecutive days

---

IEnumerable<DateTime> DateRange(DateTime start, DateTime end, TimeSpan period)
{
    for (var dt = start; dt <= end; dt = dt.Add(period))
    {
        yield return dt;
    }
}

---

public static IEnumerable<IEnumerable<T>> GroupSequenceWhile<T>(this IEnumerable<T> seq, Func<T, T, bool> condition) 
{
    List<T> list = new List<T>();
    using (var en = seq.GetEnumerator())
    {
        if (en.MoveNext())
        {
            var prev = en.Current;
            list.Add(en.Current);

            while (en.MoveNext())
            {
                if (condition(prev, en.Current))
                {
                    list.Add(en.Current);
                }
                else
                {
                    yield return list;
                    list = new List<T>();
                    list.Add(en.Current);
                }
                prev = en.Current;
            }

            if (list.Any())
                yield return list;
        }
    }
}

Answer 4

I would start with the ranges in date order based on starting date, add the first entry as a range in its entirety so:

09/26/16 - 12/31/17 at $20.00
TBD:
12/01/16 - 12/31/16 at $18.00

Next grab the next range you have, if it overlaps with the previous one, split the overlap (there are few kinds of overlaps, make sure to handle them all) taking the minimum value for the overlapped region:

09/26/16 - 11/30/16 at $20.00
12/01/16 - 12/31/16 at $18.00
TBD:
01/01/17 - 12/31/17 at $20.00

Note that you don't have the last one yet as you would take any splits that occur after and put them back into your sorted list of "yet to be compared" items.

Answer 5

Try this

lets say we have:

public class DatePrice
{
    public DateTime StartDate { get; set; }
    public DateTime EndDate { get; set; }
    public decimal Price { get; set; }
}

and

IList<DatePrice> list = new List<DatePrice>(); // populate your data from the source..
var lowestPriceItem = list.OrderBy(item => item.Price).First();

should give you the lowest price item.