计算打开事件的最大数目

本文关键字：最大数 事件 计算 | 更新日期: 2023-09-27 18:19:22

我有一个带有开放日期和关闭日期的事件列表，如下所示:

DateOpen   | DateClose
-----------|-----------
01.01.2000 | 05.01.2000
02.01.2000 | 02.01.2000

所以在01.01。我们有一场公开比赛，在02.01。我们有两场公开比赛，从那以后我们只有一场公开比赛，直到5点01分。

现在的任务是计算打开事件的最大数量，在本例中为2。

我就是找不到一个好的解决方案，也许别人有一个好主意。我有一个链接到对象列表中的所有事件，所以排序，过滤等很容易。

我试过什么了?没有，因为我不知道从哪里开始:)

计算打开事件的最大数目

这是一个遍历列表的解决方案。我还包括一个分裂对开放和关闭。(因为我认为这就是你的数据存储方式。)由于遍历需要先打开后关闭，所以我添加了s，并且不只是对日期进行排序，并且在创建Event对象时需要顺序。如果关闭在打开之前，这个操作将失败。

这是用linqpad编写和测试的。原样复制并粘贴它，它就会运行。在LinqPad.com获得它(然后爱上它)

我期望这是O(log n)因为OrderBy应该是O(log n) 

void Main()
{
  List<Event> eList = new List<Event>();
  eList.Add(new Event(new DateTime(2000,1,1),new DateTime(2000,5,1)));
  eList.Add(new Event(new DateTime(2000,2,1),new DateTime(2000,2,1)));
  var datelist = eList.Select(item => new { t = "open", d = item.open, s = item.open.Ticks*10 })
        .Concat(eList.Select(item => new { t = "close", d = item.close, s = (item.close.Ticks*10)+1 }))
        .OrderBy(item => item.s);
  var max = datelist.Aggregate(
            new { curCount = 0, max = 0 },
            (result,item) => {
               if (item.t == "open")
               {
                  if (result.max < (result.curCount+1))
                    return(new { curCount = result.curCount+1, max = result.curCount+1 });
                  else
                    return(new { curCount = result.curCount+1, max = result.max });
               }
               else
                 return(new { curCount = result.curCount-1, max = result.max });
            },
            result => result.max);
   max.Dump();
}
// Define other methods and classes here
public class Event
{
    public DateTime open { get; set; }
    public DateTime close { get; set; }
    public Event(DateTime inOpen, DateTime inClose)
    {
      if (inOpen <= inClose)
      {
        open = inOpen;
        close = inClose;
      }
      else throw(new Exception("Can't close at "+inClose.ToShortDateString()+" before you open at "+inOpen.ToShortDateString()));
    }
}

var max = events.Select(i => events.Where(j => i.DateOpen <= j.DateClose
                                            && i.DateClose >= j.DateOpen).Count())
                .Max();

但它的复杂度O(n^2)可能并不适用于所有情况

目前想不出更快的解决办法。

由于实际答案仅在注释中:

events.Select(i => events.Where(j => i.DateOpen <= j.DateClose && i.DateClose >= j.DateOpen).Count()).Max()
相关文章：