尋找算法來有效地佈置日曆事件橫幅

Question

我正在尋找一種算法來高效地放置全天/多日事件橫幅，就像在Outlook或Google日曆中的月視圖一樣。我有許多事件的開始日期和結束日期，通過增加開始日期（然後結束日期）（或您請求的任何其他順序，我從數據庫表中收集事件）進行排序。我想最大限度地減少用完的垂直空間的數量，因爲在事件橫幅之後，我需要爲當天安排其他活動（這些活動總是在特定日期的橫幅之後出現）。因此，例如，如果我有兩個事件，一個1/10-1/11和一個1/11-1/15，我寧願像這樣排列它們（每列是一天）：

bbbbb 
aa 

，而不是像：

aa 
bbbbb 

，因爲當我添加事件，只爲這一天（X，Y和Z），我可以做到這一點（我寧願第一，不想第二次） ：

bbbbb vs. aa 
aa xyz   bbbbb 
        xyz 

但它不像放置較長的事件一樣簡單，因爲機智H 1/10-1/11，1/13-1/14，和1/11-1/13，我希望：

aa cc 
bbb 

，而不是：

bbb 
aa cc 

，因爲這將允許事件x和y：

aa cc vs.  bbb 
xbbby   aa cc 
       x y 

當然，我寧願這樣做在一次通過。對於數據結構，我目前使用從日期到列表的地圖，在事件的每一天，我將事件添加到相應的列表中。因此，一個爲期三天的活動出現在三個列表中，每個列表在地圖中的一個日期之下。這是將結果轉換爲視覺輸出的便利結構，但我也對其他數據結構開放。我目前使用貪心算法，在這裏我只是爲了增加每個事件，但可以產生不必要的工件，如：

aa ccc   
bbbbb 
    dd 
    eeeeeeeeeeeeeeeee 

這種浪費的空間很多對於大多數的「E」活動的日子。

任何想法？

Answer 1

這裏是一個可能解決方案的高級草圖（使用星期幾整數而不是全部日期）。此接口：

public interface IEvent { 

    public abstract int getFirst(); // first day of event 
    public abstract int getLast(); // last day of event 
    public abstract int getLength(); // total number of days 
    public abstract char getLabel(); // one-char identifier 

    // true if this and that have NO days in common 
    public abstract boolean isCompatible(IEvent that); 

    // true if this is is compatible with all events 
    public abstract boolean isCompatibleWith(Collection<IEvent> events); 

} 

必須實現使用下面的方法layout表達的算法。

此外，具體的類必須實現Comparable創建一個自然順序，其中較長的事件先於較短的事件。 （下面我對演示示例實現使用降長度，然後上升開始日期，然後上升標籤的順序。）

的layout方法採用IEvent實例的集合，並返回一個Map指派到每一行中的呈現可以在該行中顯示的一組事件。

public Map<Integer,Set<IEvent>> layout(Collection<IEvent> events) { 
    Set<IEvent> remainingEvents = new TreeSet<IEvent>(events); 
    Map<Integer,Set<IEvent>> result = new TreeMap<Integer,Set<IEvent>>(); 
    int day = 0; 
    while (0 < remainingEvents.size()) { 
     Set<IEvent> dayEvents = new TreeSet<IEvent>(); 
     for(IEvent e : remainingEvents) { 
      if (e.isCompatibleWith(dayEvents)) { 
       dayEvents.add(e); 
      } 
     } 
     remainingEvents.removeAll(dayEvents); 
     result.put(day, dayEvents); 
     ++day; 
    } 
    return result; 
} 

每一行是通過選擇剩餘的最長事件和逐步選擇所有其他事件（在上面所描述的順序），其與當前行先前選擇的事件兼容組成。其效果是所有事件儘可能向上「浮動」而不會發生碰撞。

以下演示顯示了您的問題中的兩種情況，以及隨機創建的一組事件。

Event collection: 
    x(1):4 
    b(5):2..6 
    y(1):5 
    a(2):1..2 
    z(1):6 
Result of layout: 
    0 -> {b(5):2..6} 
    1 -> {a(2):1..2, x(1):4, y(1):5, z(1):6} 
Visual presentation: 
     bbbbb 
    aa xyz 

Event collection: 
    x(1):1 
    b(3):2..4 
    a(2):1..2 
    c(2):4..5 
    y(1):5 
Result of layout: 
    0 -> {b(3):2..4, x(1):1, y(1):5} 
    1 -> {a(2):1..2, c(2):4..5} 
Visual presentation: 
    xbbby 
    aa cc 

Event collection: 
    f(2):1..2 
    h(2):1..2 
    d(4):1..4 
    e(4):2..5 
    c(1):6 
    a(2):5..6 
    g(4):2..5 
    b(2):0..1 
Result of layout: 
    0 -> {d(4):1..4, a(2):5..6} 
    1 -> {e(4):2..5, b(2):0..1, c(1):6} 
    2 -> {g(4):2..5} 
    3 -> {f(2):1..2} 
    4 -> {h(2):1..2} 
Visual presentation: 
    ddddaa 
    bbeeeec 
     gggg 
    ff  
    hh  

Answer 2

我認爲在這樣的情況下，確保您的數據首先正確組織，然後再進行渲染會更好。我知道你想要一次傳球，但我認爲結果會更好。

例如，將數據組織成您需要在特定日期擁有的行，並以最好的方式組織事件，從最長的事件開始（不需要首先顯示，但它們確實需要首先組織），並向下移動到最短的事件。這將允許您相應地呈現您的輸出，而不會浪費任何空間，並避免這些「e」事件日。此外，則：

bbb 
aa cc 

或

aa cc 
bbb 

不會不要緊，因爲x和y總是可以的bbb或甚至aa和cc

兩邊去，我希望你能找到這個很有幫助。