0

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

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

所以在 01.01。我们在 02.01 举办了一场公开活动。我们有两个公开活动，从那里我们只有一个公开活动，直到 05.01。

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

我只是找不到一个好的解决方案，也许其他人有一个好主意。我有一个 linq-to-objects 列表中的所有事件，因此排序、过滤等很容易。

我尝试了什么？没什么，因为我不知道从哪里开始 :)

4

3 回答 3

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

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

虽然目前无法想到更快的解决方案。

于 2013-06-21T02:30:25.823 回答
1

这是一个清单解决方案。我还包括一个拆分打开和关闭的对。（因为我希望这就是您的数据的存储方式。）由于步行需要在关闭之前打开，因此我在 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()));
    }
}
于 2013-06-21T03:40:43.897 回答
0

由于实际答案仅在评论中：

events.Select(i => events.Where(j => i.DateOpen <= j.DateClose && i.DateClose >= j.DateOpen).Count()).Max()
于 2013-06-21T01:39:58.067 回答