カレンダーイベントバナーを効率的にレイアウトするためのアルゴリズムを探しています
https://stackoverflow.com/questions/400288
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
OutlookやGoogleカレンダーの月表示のように、終日/複数日イベントバナーを効率的に配置するアルゴリズムを探しています。開始日（および終了日）の昇順（またはデータベーステーブルからイベントを収集している他の任意の順序）で順序付けられた、開始日と終了日を持つイベントがいくつかあります。イベントバナーの後にその日だけ他のイベントを配置する必要があるため、使用される垂直方向のスペースの平均量を最小限にしたいと思います（これらは常に特定の日付のバナーの後に来ます）。したがって、たとえば、2つのイベント（1つは1 / 10-1 / 11と1つは1 / 11-1 / 15）がある場合、そのように配置することをお勧めします（各列は1日）：
bbbbb
aa
そして好きではない：
aa
bbbbb
1日（x、y、およびz）のイベントのみを追加する場合、これを行うことができます（最初のイベントを希望し、2番目のイベントは希望しません）：
bbbbb vs. aa
aa xyz bbbbb
xyz
しかし、1 / 1-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
そしてもちろん、1回のパスでこれを行いたいと思います。データ構造では、現在、日付からリストへのマップを使用しています。イベントの各日について、対応するリストにイベントを追加します。したがって、3日間のイベントは3つのリストに表示され、各リストはマップのいずれかの日の下にあります。これは、結果を視覚的な出力に変換するための便利な構造ですが、他のデータ構造も利用できます。現在、貪欲なアルゴリズムを使用しています。各イベントを順番に追加するだけですが、次のような不要なアーティファクトが生成される可能性があります。
aa ccc
bbbbb
dd
eeeeeeeeeeeeeeeee
これにより、ほとんどの＆quot; e＆quot;の多くのスペースが無駄になります。イベント日。
アイデアはありますか
解決
これは、考えられる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;
}
各行は、残りの最長イベントを選択し、現在の行で以前に選択したイベントと互換性のあるすべての追加イベントを（上記の順序で）段階的に選択することで構成されます。その効果は、すべてのイベントが「フロート」することです。衝突することなく可能な限り上向きに。
次のデモでは、ランダムに作成された一連のイベントとともに、質問の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
他のヒント
このような状況では、まずデータを適切に整理してからレンダリングすることをお勧めします。シングルパスが必要なことは知っていますが、結果はかなり良くなると思います。
たとえば、特定の日に必要な行にデータを整理し、最長のイベントから始めて、可能な限りイベントを整理します（最初に表示する必要はありませんが、最初に組織されます）、最短のイベントに移動します。これにより、スペースを無駄にせずに出力をレンダリングし、「e」を回避できます。イベントの日。さらに、次に：
bbb
aa cc
または
aa cc
bbb
x および y は常に bbb のいずれかの側、または aa および cc
これがお役に立てば幸いです。
