0

Outlook や Google カレンダーの月表示のように、終日/複数日のイベント バナーを効率的に配置するアルゴリズムを探しています。開始日と終了日が指定されたイベントが多数あり、開始日 (および終了日) の昇順に並べられています (または、データベース テーブルからイベントを収集しています)。イベントバナーの後には、その日だけ他のイベントを配置する必要があるため、使用される垂直方向のスペースの平均量を最小限に抑えたいと考えています (これらは常に、特定の日付のバナーの後に配置されます)。したがって、たとえば、1/10-1/11 と 1/11-1/15 の 2 つのイベントがある場合、次のように配置することをお勧めします (各列は 1 日です)。

 bbbbb
aa

そして好きではない：

aa
 bbbbb

その日 (x、y、および z) だけのイベントを追加すると、これを行うことができるためです (最初のほうが好きで、2 番目は必要ありません)。

 bbbbb    vs.    aa
aa xyz            bbbbb
                    xyz

しかし、長いイベントを最初に配置するほど単純ではありません。

aa cc
 bbb

とは対照的に：

 bbb
aa cc

これは、イベント x および y を許可するためです。

aa cc    vs.     bbb
xbbby           aa cc
                x   y

そしてもちろん、私はこれを 1 回のパスで行うことを好みます。データ構造については、現在、日付からリストへのマップを使用しており、イベントの日ごとに対応するリストにイベントを追加しています。そのため、3 日間のイベントが 3 つのリストに表示され、それぞれがマップ内の 1 日の下に表示されます。これは、結果を視覚的な出力に変換するための便利な構造ですが、他のデータ構造も受け入れています。私は現在、各イベントを順番に追加する貪欲なアルゴリズムを使用していますが、次のような不要なアーティファクトが生成される可能性があります。

aa ccc          
 bbbbb
    dd
     eeeeeeeeeeeeeeeee

これにより、ほとんどの「e」イベント日で多くのスペースが無駄になります。

何か案は？

4

2 に答える 2

6

以下は、考えられる解決策の 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のコレクションを受け取り、プレゼンテーションの各行に、その行に表示できる一連のイベントを割り当てる を返します。IEventMap

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;
}

各行は、残りの最も長いイベントを選択し、現在の行で以前に選択されたイベントと互換性のあるすべての追加イベントを (上記の順序で) 徐々に選択することによって構成されます。その効果は、すべてのイベントが衝突することなく可能な限り上向きに「浮く」ということです。

次のデモは、質問の 2 つのシナリオと、ランダムに作成された一連のイベントを示しています。

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
于 2008-12-31T21:34:34.083 に答える
0

このような状況では、まずデータが適切に整理されていることを確認してからレンダリングする方がはるかに優れていると思います。1回のパスが必要なことは承知していますが、結果ははるかに優れていると思います.

たとえば、特定の日に必要な行にデータを整理し、最も長いイベントから始めて、可能な限り最善の方法でイベントを整理します (最初に表示する必要はありませんが、整理する必要があります)。最初) 最短のイベントに移動します。これにより、スペースを無駄にすることなく出力を適切にレンダリングし、それらの「e」イベント日を回避できます。さらに、次のようになります。

 bbb
aa cc

また

aa cc
 bbb

xandyはいつでも and のいずれかの側bbbまたは間aaで使用できるため、重要ではありません。cc

これがお役に立てば幸いです。

于 2008-12-30T14:50:32.950 に答える