寻求一种算法来有效地布局日历事件横幅

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

但它并不像首先放置较长的事件那么简单,因为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