寻求一种有效布局日历活动横幅的算法

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    

Answer 2

我认为在这种情况下，最好先确保数据组织正确，然后再渲染。 我知道你想要一次通过，但我认为结果会好得多。

例如，将数据组织成给定日期所需的行，并以尽可能最好的方式组织事件，从最长的事件开始（不需要首先显示，但确实需要组织）首先）并向下移动到最短的事件。 这将使您能够相应地渲染输出，而不浪费任何空间，并避免那些“e”事件日。 另外，那么：

 bbb
aa cc

or

aa cc
 bbb

并不重要，因为 x 和 y 始终可以位于 bbb 的任一侧，甚至位于 aa< 之间/code> 和 cc

我希望这对您有所帮助。