查找重叠日期范围的最低价格 - C# 算法

Question

有特定时间段的价格...我无法想出一种算法来确定特定时间段的最低价格。

我正在使用对象列表执行此操作，其中对象具有属性 DateTime StartDate, DateTime EndDate, decimal Price。

例如，两个价格集及其有效日期范围：

A. 09/26/16 - 12/31/17 at .00
B. 12/01/16 - 12/31/16 at .00

可以看到B在A时间段内，并且更低。

我需要将其转换为：

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

它必须适用于任意数量的日期范围和组合。有没有人遇到过任何我可以操纵以获得我需要的结果的东西？或者有什么建议吗？

编辑：我的数据结构：

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

我将从基于开始日期的日期顺序的范围开始，将第一个条目添加为整个范围，因此：

09/26/16 - 12/31/17 at .00
TBD:
12/01/16 - 12/31/16 at .00

接下来抓取你的下一个范围，如果它与前一个范围重叠，则将重叠部分分开（重叠部分很少，一定要处理好）取重叠区域的最小值：

09/26/16 - 11/30/16 at .00
12/01/16 - 12/31/16 at .00
TBD:
01/01/17 - 12/31/17 at .00

请注意，您还没有最后一个，因为您会将之后发生的任何拆分放回 "yet to be compared" 项目的排序列表中。

Answer 2

试试这个

假设我们有：

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

和

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

应该给你最低价的商品。

Answer 3

这是使用 Linq 的绝佳案例。假设您的价格范围对象称为 PriceRecord...

您需要创建一个包含所有日期的列表，然后筛选出两个连续日期之间的价格记录。一个实现可能看起来像这样：

    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 };
        }
    }

~~我还没有对此进行测试，您可能需要修改比较运算符，但这可能是一个很好的起点。~~ 我现在已经测试了代码，这里的例子适用于问题中的数据。

欢迎提出修改建议以改进此示例。

Answer 4

没有直接回答你的问题，但这里有一些 SQL 我用来解决我遇到的类似问题（简化了一点，因为我也在处理多个地点和不同的价格类型):

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 来自其中 RowNumBtl=1 表示 UnitPrice 和 RowNumCase=1 表示 CasePrice。如果您随后创建 table 个日期（您可以使用 CTE 执行此操作），则可以在每个日期交叉应用。这有点低效，因为您只需要在日期范围之间的边界条件下进行测试，所以...祝您好运。

Answer 5

我将使用 2 个函数 DateRange 和 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));
}

输出：

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

算法：

1- 为 promoResult 列表中的每个项目创建一个 <day,price> 元组

2- 按天和 select 最低价格

将此元组分组

3- 按日期排序此元组

4-select连续几天价格变化的起止日

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;
        }
    }
}

查找重叠日期范围的最低价格 - C# 算法

Finding lowest price for overlapping date ranges - C# algorithm

c#

algorithm

date-range