計算打開的事件最大數量

我有一個事件列表以開放和關閉日期，就像這樣：計算打開的事件最大數量

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

所以在01.01。我們在02.01有一個開放的活動。我們有兩場公開賽，從那裏我們只有一場公開賽直到05.01。

現在的任務是計算open事件的最大數量，在這個例子中是2

我只是找不到這一個很好的解決方案，也許別人有個好主意。我把所有的事件都放在一個linq-to-objects列表中，所以排序，過濾等都很簡單。

我試過了什麼？沒有什麼，因爲我不知道從哪裏開始:)

來源

2013-06-21 Marc

'events.Select（I => events.Where（J => i.DateOpen <= j.DateClose && i.DateClose> = j.DateOpen）.Count之間（））。MAX（）'（我現在不編程C＃，所以可能會錯過一些東西） – zerkms

@zerkms：這可能會起作用。它是O（n^2），但對於這個應用程序來說可能很好。 – Gabe

@加貝：我正在考慮一些樹結構，但並沒有將它們應用於有限的時間間隔。 – zerkms

這是散步列表解決方案。我也包括一對開放和關閉。（因爲我期望這就是你的數據存儲的方式。）由於步行需要在關閉之前打開，所以我在s中添加了它，並且不僅僅按日期排序，並且需要創建Event對象的順序。如果收盤時有收盤價出現，這將失敗。

這是用linqpad編寫和測試的。將它複製並粘貼，並且它將會運行。得到它（然後愛它）在LinqPad.com

我期望這是O（日誌n），因爲OrderBy應該是O（日誌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-21 03:40:43 Hogan

是的，我現在看到。不過，我認爲它是'O（n logn）'，因爲它是作爲一個穩定的快速排序 – zerkms

作爲一種替代方法，你也可以將它轉換爲'open'，'close'字符串（或bools，或其他）的列表，在每個「關閉」上打開'++'計數器和'--'。記住達到的最大值 – zerkms

哇，謝謝大家的回答，這個很棒！ +1，接受和更多，如果我可以:)非常感謝！ – Marc

由於實際的答案是唯一的一個評論：

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

來源

2013-06-21 01:39:58 ericdc

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

但它是一個複雜O(n^2)這可能不適合所有的案例

儘管目前還不能想到更快的解決方案。

來源

2013-06-21 02:30:25 zerkms

你可以在O（N lg（N））中通過排序打開和關閉時間，然後走他們以跟蹤當前打開事件的數量（以及打開事件的最大數量）。 – Gabe

@加貝：「爲了跟蹤當前開放事件的數量而行走它們」---這就是問題所在，不是嗎？ – zerkms

非常感謝！我剛剛嘗試過，但它給了我更多的公開事件（但我必須仔細檢查以確保它不是我在數據中的錯誤）。 – Marc

計算打開的事件最大數量

回答

相關問題